Objekt-Metadaten

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

HaupttitelOn mutually avoiding sets
AutorValtr, Pavel
Institution/KörperschaftUniversität <Berlin, Freie Universität> / Fachbereich Mathematik und Informatik
Seitenzahl6 S.
Schriftenreihe Freie Universität Berlin, Fachbereich Mathematik : Ser. B ; 94,5
DDC004 Datenverarbeitung; Informatik
ZusammenfassungTwo 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.
Dokumente
pdf-Datei
Falls Ihr Browser eine Datei nicht öffnen kann, die Datei zuerst herunterladen und dann öffnen.
 
Fachbereich/EinrichtungFB Mathematik und Informatik
Arbeitsbereich/InstitutInstitut für Informatik
Erscheinungsjahr1994
Dokumententyp/-SammlungenArbeitspapier
SpracheEnglisch
Rechte Nutzungsbedingungen
Erstellt am12.03.2009 - 09:04:42
Letzte Änderung27.02.2015 - 08:24:52
 
Statische URLhttp://edocs.fu-berlin.de/docs/receive/FUDOCS_document_000000001112
Zugriffsstatistik
 

LOADING...