Seminar Algorithmische Geometrie Leitung: Dr. Dahlhaus Referent: Martin L¨ ohnertz

Voronoidiagramm und Delaunytriangulierung

1. Allgemeine Eigenschaften von Voronoidiagramm und Delaunytriangulierung

• Zu einer gegebenen Metrik und einer Menge von Objekten (Sites) bezeichnet das Voronoidiagramm die Menge von Punkten, die die Regionen mit jeweils verschiedenen ”n¨ achstgelegenen” Objekten begrenzen.

• Im Fall der euklidischen Metrik und von Punktsites handelt es sich um einen planaren, sogar konvexen Graphen mit O(n) Knoten und Kanten.

• Als Knoten sieht man dabei diejenigen Punkte an, die auf dem Ber¨ uhrungspunkt mindestens dreier Regionen liegen. Be�nden sich die Sites nicht in allgemeiner Lage, d.h. liegen 4 davon auf einem leeren Kreis, so k¨ onnen sich auch mehr als 3 Regionen in einem Knoten ber¨ uhren.

• Zu je zwei benachbarten Regionen existiert ein Kreis, der die beiden Sites ber¨ uhrt und im Inneren keine weitere enth¨ alt.

• Die Delaunytriangulation ist der duale Graph zu diesem Graphen.

• DT ist die Triangulation mit der gr¨ oßten Winkelfolge.

• Der minimale Spannbaum ist Teilgraph der DT.

2. Das Sweepline Paradigma

• ¨ Ubertragung eines Problemes in n Dimensionen in ein n − 1 dimensionales, indem eine Koordinate in eine Zeitachse umgewandelt wird.

• Ereignisgesteuerte Simulation der Bewegung einer n − 1 dimensionalen Hyperebene durch den Gesamtraum

• H¨ au�g beh¨ alt man einige der besuchten Punkte ”einige Zeit im Ged¨ achtnis”, niemals aber alle.

3. Die Transformation ⋆

Sei d(z) die Entfernung zur n¨ achstgelegenen Site. d_{p}(z) die zur Site p. • ⋆((x, y)) := (x, y + d((x, y))) ⋆_{p}((x, y)) := (x, y + d_{p}((x, y)))

• ⋆ und ⋆_{p} sind auf der Voronoi-Region von p identisch.

• ⋆_{p} bildet nicht senkrechte Graden auf Hyperbeln und senkrechte Graden auf Strahlen ab.

• unter ⋆ wird jede Site zu dem Punkt ihrer Region mit der kleinsten y-Koordinate und in jeden Schnittpunkt f¨ uhren von unten mindestens zwei Kanten.

• ⋆ ist auf VD eineindeutig und die Identit¨ at auf Sites.

4. Ein Sweepline-Algorithmus zur Bestimmung des Voronoidiagrammes

• Zur jeweiligen Position der Sweepline, die sich von den kleinen zu den großen y-Koordinaten bewegt, speichert man die jeweils geschnittenen Regionen von ⋆(V D) zusammen mit den trennenden Kanten.

• Die Priorit¨ atswarteschlange der noch ausstehenden Ereignisse enth¨ alt alle noch nicht besuchten Sites, sowie alle Schnittpunkte von benachbarten Kanten in der Regionenliste.

• Beide Strukturen k¨ onnen sichr nur an Sites und Schnittpunkten ¨ andern.

• der Algorithmus verschiebt die Sweepline also immer bis zum n¨ achsten ”Ereignis” und korrigiert dort die Daten entsprechend.

• Schnittpunkte von trennenden Kanten k¨ onnen als Knoten des V D ausgegeben werden, bzw. implizieren ein Dreieck der DT.

• Der Algorithmus berechnet ⋆(V D), kann aber in einem VD und DT ausgeben, bzw. VD zum Berechnen von ⋆(V D) heranziehen.

• Die Laufzeit ist O(n log n) und somit asymptotisch optimal. Der logarithmische Faktor kommt durch die Priority-Queue und das Suchen in der Regionenliste zustande.

5. Verallgemeinerungen

(a) Linien-Sites

• das Problem der Liniensegmente wird vereinfacht, indem man Segmente und Endpunkte getrennt betrachtet. Die Bisektoren sind dann Parabalst¨ ucke und Liniensegmente.

• Es kann die gleiche Transformation angewandt werden, es werden allerdings ganze Gebiete unter horizontalen Linien-Sites mit der Linie identi�ziert.

• Due F¨ alle, in denen sich mehrere Bisektoren in einem Punkt treffen, m¨ ussen gesondert betrachtet werden.

(b) gewichtete Punkt-Sites • Zu jedem Abstand wird ein von der Site abh¨ aniger Wert w_{q} addiert.

• Die Transformation wird durch ⋆((x, y)) := (x, y + d((x, y)) + w_{s}) ersetzt, wobei w_{s} die n¨ achstgelegene Site ist.

• Sites werden gem¨ aß ihres w nach oben verschoben.

• Eine Site kann ihr Gebiet vollkomen an andere Sites verlieren. Dies muß ¨ uberpr¨ uft werden.

• Bisektoren und transformierte Bisektoren sind Hyperbeln. Die Schnittpunkte k¨ onnen berechnet werden.

• Die Bilder der Sites sind die untersten Punkte der transformierten Regionen und in jeden Schnittpunkt f¨ uhren von unten zwei Kanten.

6. Literatur

• Fortune, S.: A Sweepline Algorithm for Voroni Diagrams; Algorithmica 2,1987

• Klein, Rolf: Algorithmische Geometrie ; Bonn: Addison-Wesley 1997