Ph.D. thesis : Planar point sets with bounded ratios of distances

Pavel Valtr

Advisor: Prof. Dr. Emo Welzl

Eine n -elemente Punktmenge A in der Ebene heißt dicht , wenn das Verhältnis zwischen dem maximalen und dem minimalen Abstand von zwei Punkten in A von der Größenordnung O (\sqtr{n}) ist. In dieser Arbeit wurden folgende fünf Hauptergebnisse über dichte Mengen gezeigt:

1. Die konvexe Hülle einer dichten Menge kann in linearer Zeit berechnet werden.
2. Die Größe von zwei greichgroßen paarweise vermeidenden Untermengen beliebiger dichten Menge von n Punkten ist nicht größer als O (\sqtr{ n }). (Zwei Punktmengen in der Ebene heißen paarweise vermeidend , wenn keine Gerade, die durch zwei Punkte aus einer der zwei Punktmengen geht, die konvexe Hülle der anderen Punktmenge schneidet.)
3. Sei \Epsilon > 0 eine Konstante. Dann enthät jede dichte Menge von n Punkten die Endpunkte von \Omega (n ^ { 1- \epsilon }) Segmenten, die sich paarweise schneiden.
4. Für jedes gerade n \in N gibt es eine dichte Punktmenge von n Punkten, für die \Omega (n log n) halbierenden Geraden existieren. Andererseits gibt es für jede dichte Punktmenge von n Punkten nicht mehr als \Omega (n ^ { 4/5 } / log* n) halbierenden Geraden. (Eine Gerade heißt halbierend für eine Punktmenge A in der Ebene, wenn sie durch zwei Punkten in A geht und die Menge A in zwei gleichgroße Teile schneidet.)
5. Jede dichte Punktmenge der Größe n enthät \Omega (n ^ { 1/3 }) Knoten eines konvexen Polygons. Die Schranke \Omega (n ^ { 1/3 }) ist scharf, weil in einem bestimmten natürlichen Sinn die meisten dichten Punktmengen der Gröe n nicht mehr als O (n ^ { 1/3 }) Knoten eines konvexen Punktes enthalten.