Objekt-Metadaten

On mutually avoiding sets
Valtr, Pavel ;  Universität <Berlin, Freie Universität> / Fachbereich Mathematik und Informatik

Main titleOn mutually avoiding sets
AuthorValtr, Pavel
InstitutionUniversität <Berlin, Freie Universität> / Fachbereich Mathematik und Informatik
No. of Pages6 S.
Series Freie Universität Berlin, Fachbereich Mathematik : Ser. B ; 94,5
Classification (DDC)004 Data processing and Computer science
AbstractTwo finite sets of points in the plane are called mutually avoiding if any straight line passing through two points of anyone of these two sets does not intersect the convex hull of the other set. For any integer n, we construct a set of n points in general position in the plane which contains no pair of mutually avoiding sets of size more than O (n). The given bound is tight up to a constant factor, since Aronov et al. [AEGKKPS] showed a polynomial time algorithm for finding two mutually avoiding sets of size (n) in any set of n points in general position in the plane.
Documents
pdf-Datei
If your browser can't open the file, please download the file first and then open it
 
FU DepartmentDepartment of Mathematics and Computer Science
Other affiliation(s)Institut für Informatik
Year of publication1994
Type of documentWorking paper
LanguageEnglish
Terms of use/Rights Nutzungsbedingungen
Created at2009-03-12 : 09:04:42
Last changed2015-02-27 : 08:24:52
 
Static URLhttp://edocs.fu-berlin.de/docs/receive/FUDOCS_document_000000001112
Statistics
 

LOADING...