Computational Geometry in C - Arrangements

Computational Geometry (Algorithmische Geometrie) befasst sich mit Entwurf, Analyse und Implementierung von Algorithmen zur Lösung geometrischer Probleme auf einem Rechner. Die Anwendungsbereiche sind vielfältig: CAD, Animation, Computergrafik, Simulation, Verarbeitung geographischer Daten, medizinische Anwendungen, Robotik, etc. In dem Proeminar wurde eine Auswahl der wichtigsten Algorithmen und Datenstrukturen vorgestellt.

Arrangements

Arrangements von Geraden (und Ebenen) bilden, neben Konvexen Hüllen und Voronoi Diagrammen, die dritte bedeutende Struktur, die in der Computational Geometry genutzt wird.

Definition Arrangement:

Gegeben sei eine Menge von (unendlich vielen) Geraden, die in einer Ebene angeordnet (arranged) sind. Diese Geraden bewirken eine Partition der Ebene in:

• konvexe Polygone, die als Zellen (cells) oder Facetten (faces) bezeichnet werden
• Segmente oder Kanten (edges) zwischen den Schnittpunkten der Geraden
• Knoten (vertices), wo sich die Geraden schneiden

Es ist diese Partition, die als Arrangement bezeichnet wird.

Arrangements erscheinen viel zu abstrakt, um viele Anwendungen zu haben, aber in Wirklichkeit gibt es eine ganze Reihe davon. An dieser Stelle sollen zwei Beispiele genügen:

• Hidden Surface Removal: Als Hidden Surface Removal wird die Ermittlung der verdeckten Objekte in einer dreidimensionalen Szene bezeichnet. Der erste Worst-Case optimale Θ(n²) Algorithmus basiert auf Arrangements.
• Ham-Sandwich Cuts: Es gibt einen bemerkenswerten Satz, der besagt, dass jedes Schinken-Sandwich so von einer Ebene geschnitten werden kann, dass beide Hälften die gleiche Menge an Schinken und Brot enthalten. Die zweidimensionale Version dieses Satzes besagt, dass immer eine Gerade existiert, die zwei Punktmengen genau halbiert. Arrangements ermöglichen es, diese Halbierung in linearer Zeit zu finden, also O(n), wobei n die Anzahl der Punkte ist.

Download Ausarbeitung

• Ausarbeitung (PS) [ 825 kB]