Seminar Computational Geometry Convex Hull

Seminar Computational GeometrySeminar Computational Geometry

Convex HullConvex HullChristian SteinChristian Stein

GliederungGliederung

1. Definition1. Definition

2. Motivation2. Motivation

3. Algorithmische Ansätze3. Algorithmische Ansätze

4. Incremental-Algorithmus mit 4. Incremental-Algorithmus mit Konfliktgraph Konfliktgraph

5. Laufzeitanalyse 5. Laufzeitanalyse


Betrachtung :Betrachtung : Punktemenge repräsentiert durch Punktemenge repräsentiert durch

umgebendes Polygonumgebendes Polygon Rand des Polygons undurchsichtigRand des Polygons undurchsichtig

Für alle Punkte p, q innerhalb des Für alle Punkte p, q innerhalb des Polygons :Polygons : p ist von q aus sichtbar, wenn die minimale p ist von q aus sichtbar, wenn die minimale

Verbindungsstrecke zwischen p und q ganz Verbindungsstrecke zwischen p und q ganz im Polygon enthalten ist.im Polygon enthalten ist.


Polygon ist : Polygon ist : sternförmig – wenn von einem Punkte p alle anderen sternförmig – wenn von einem Punkte p alle anderen

sichtbar sindsichtbar sind Konvex – wenn von Konvex – wenn von jedemjedem Punkt p alle anderen Punkt p alle anderen

sichtbar sind. sichtbar sind.

(a) konvex - (b) sternförmig (a) konvex - (b) sternförmig


Übertragen auf Punktmenge :Übertragen auf Punktmenge : Konvexes Polygon wird erzeugt durch konvexe Konvexes Polygon wird erzeugt durch konvexe

Hülle einer Menge MHülle einer Menge M Konvexe Hülle von M ist die kleinste konvexe Konvexe Hülle von M ist die kleinste konvexe

Menge die M umschließtMenge die M umschließt

Leicht vorstellbar :Leicht vorstellbar : Punkte sind Nägel auf einer EbenePunkte sind Nägel auf einer Ebene -> Konvexe Hülle = Nägel umspannendes -> Konvexe Hülle = Nägel umspannendes

GummibandGummiband

1. Definition 1. Definition

Problem Konvexe HülleProblem Konvexe Hülle Eingabe : endliche Menge M von Punkten in der Eingabe : endliche Menge M von Punkten in der

EbeneEbene Ausgabe : diejenigen Punkte von Ausgabe : diejenigen Punkte von MM, die den Rand , die den Rand

des konvexen Hüllpolygons von des konvexen Hüllpolygons von MM definieren, in definieren, in umlaufender Reihenfolge. (2D) umlaufender Reihenfolge. (2D)


Anwendung Konvexer Hüllen :Anwendung Konvexer Hüllen : Kollisionserkennung Kollisionserkennung

Kollision konvexer Hüllen schneller zu berechnen Kollision konvexer Hüllen schneller zu berechnen als Kollision der Objekte, die sie umschließenals Kollision der Objekte, die sie umschließen

Kollidieren die Hüllen nicht, kollidieren auch die Kollidieren die Hüllen nicht, kollidieren auch die Objekte nichtObjekte nicht


Anwendung konvexer Hüllen:Anwendung konvexer Hüllen: ObjektapproximationObjektapproximation

Innerhalb/Außerhalb-LageentscheidungInnerhalb/Außerhalb-Lageentscheidung

näherungsweise Volumenberechnungnäherungsweise Volumenberechnung Allgemein:Allgemein:

bessere Objektapproximation möglich als bessere Objektapproximation möglich als beispielsweise durch „Bounding-Spheres“ oder beispielsweise durch „Bounding-Spheres“ oder „Bounding-Boxes“„Bounding-Boxes“

Berechnungen dagegen schwieriger Berechnungen dagegen schwieriger


Rendering :Rendering : Raytracer : Lichtstrahl-Objekt-Schnitt kann Raytracer : Lichtstrahl-Objekt-Schnitt kann

einfacher ausgeschlossen werden. einfacher ausgeschlossen werden. konvexe Hülle nicht sichtbar -> Objekt nicht konvexe Hülle nicht sichtbar -> Objekt nicht

sichtbar => Aufwändiges Rendern des sichtbar => Aufwändiges Rendern des komplexen Objektes entfälltkomplexen Objektes entfällt


2D :2D : Viele simple Ansätze Viele simple Ansätze Gute LaufzeitenGute Laufzeiten

3D :3D : Weiterentwicklung der 2D-LösungenWeiterentwicklung der 2D-Lösungen Laufzeiten schwer zu verbessernLaufzeiten schwer zu verbessern


2D :2D : Slow-Convex-HullSlow-Convex-Hull Graham-Scan-AlgorithmusGraham-Scan-Algorithmus Javis-March-AlgorithmusJavis-March-Algorithmus

3D :3D : Gift-wrappingGift-wrapping Divide-and-Conquer-AlgorithmusDivide-and-Conquer-Algorithmus Incremental-Algorithmus (Punkt 4 und 5)Incremental-Algorithmus (Punkt 4 und 5)


Slow-Convex-HullSlow-Convex-Hull Algorithmus :Algorithmus :

1. für alle geordneten Paare p, q aus M mit p != q1. für alle geordneten Paare p, q aus M mit p != q

2. 2. überprüfe ob alle Punkte r != p & != q rechts der Kanteüberprüfe ob alle Punkte r != p & != q rechts der Kante

p nach q liegenp nach q liegen

3.3. falls „wahr“ -> füge die Kante p-q zur Kantenmenge CH falls „wahr“ -> füge die Kante p-q zur Kantenmenge CH hinzuhinzu

4. Kantenmenge CH = Kanten der Konvexen Hülle – Punkte 4. Kantenmenge CH = Kanten der Konvexen Hülle – Punkte lassen sich in gewünschter Reihenfolge heraussortierenlassen sich in gewünschter Reihenfolge heraussortieren

3. Algorithmische Ansätz3. Algorithmische Ansätz

Slow-Convex-HullSlow-Convex-Hull Laufzeit : Laufzeit :

n²-n Paare werden mit n-2 anderen Punkten n²-n Paare werden mit n-2 anderen Punkten verglichenverglichen

Laufzeit : O (n³) Laufzeit : O (n³)


Graham-Scan-AlgorithmusGraham-Scan-Algorithmus Algorithmus :Algorithmus :

1. Suche Punkt q mit minimaler y-Koordinate (& x-Koordinate)1. Suche Punkt q mit minimaler y-Koordinate (& x-Koordinate)

2. Bestimme Winkel von q zu allen weiteren Punkten entgegen 2. Bestimme Winkel von q zu allen weiteren Punkten entgegen

Uhrzeigersinn und sortiere nach den Winkeln (Bei Uhrzeigersinn und sortiere nach den Winkeln (Bei gleichengleichen

Winkeln nach Abstand absteigend)Winkeln nach Abstand absteigend)

3. Verbinde Punkte durch Polygonzug3. Verbinde Punkte durch Polygonzug

4. Durchlaufe ausgehend von q den Polygonzug und überbrücke 4. Durchlaufe ausgehend von q den Polygonzug und überbrücke konkave Ecken konkave Ecken


Graham-Scan-AlgorithmusGraham-Scan-Algorithmus Laufzeit :Laufzeit :

es werden n Winkel betrachtet -> n Schrittees werden n Winkel betrachtet -> n Schritte

Sortieren (bestmöglich n log n)Sortieren (bestmöglich n log n)

Lauf über n Punkte -> n SchritteLauf über n Punkte -> n Schritte

Laufzeit: O(n log n) Laufzeit: O(n log n)


Javis-March-AlgorithmusJavis-March-Algorithmus AlgorithmusAlgorithmus

1. 1. Starte mit Punkt q = q0 =Punkt mit minimaler y-Koordinate (& x-Starte mit Punkt q = q0 =Punkt mit minimaler y-Koordinate (& x-Koordinate) – q0 in PunktlisteKoordinate) – q0 in Punktliste

2. Solange p != q0 wiederhole:2. Solange p != q0 wiederhole:3.3. Suche von q ausgehen den „am weitesten Suche von q ausgehen den „am weitesten

rechts“ rechts“ liegenden Punkt p (alle anderen Punkte liegenden Punkt p (alle anderen Punkte

liegen links liegen links von q-p) von q-p) 4.4. Füge p zur Punktliste hinzuFüge p zur Punktliste hinzu5.5. q = pq = p

Die Punktliste enthält die Punkte der Konvexen Hülle, sortiert in Die Punktliste enthält die Punkte der Konvexen Hülle, sortiert in Richtung gegen den UrzeigersinnRichtung gegen den Urzeigersinn


Javis-March-AlgorithmusJavis-March-Algorithmus Laufzeit :Laufzeit :

Suche des kleinsten y-Wertes = O(n)Suche des kleinsten y-Wertes = O(n)

Schleife wird h-mal durchlaufen (h = Anzahl der Schleife wird h-mal durchlaufen (h = Anzahl der

Ecken der konvexen Hülle )Ecken der konvexen Hülle )

Bestimmung des „am weitesten rechts“ liegenden Bestimmung des „am weitesten rechts“ liegenden

Punktes = O(n) Punktes = O(n)

Laufzeit : O(n*h) somit im schlechtesten Fall Laufzeit : O(n*h) somit im schlechtesten Fall

( n Ecken) O(n²) ( n Ecken) O(n²)


2D -> 3D :2D -> 3D : Welche Lösungen lassen sich gut ins 3-Welche Lösungen lassen sich gut ins 3-

dimensionale Übertragen ?dimensionale Übertragen ? Beispiel :Beispiel :

Javis-March -> GiftwrappingJavis-March -> Giftwrapping


Im weiteren :Im weiteren : Facette eines konvexen Polytops ist notwendigerweise ein Facette eines konvexen Polytops ist notwendigerweise ein

konvexes Polygonkonvexes Polygon

2D : konvexes Polygon hat gleich viele Ecken p wie Kanten e2D : konvexes Polygon hat gleich viele Ecken p wie Kanten e

3D : Satz von Euler :3D : Satz von Euler : n – n(e) + n(f) = 2n – n(e) + n(f) = 2

n Anzahl der Punkten Anzahl der Punkte

n(e) Anzahl der Kanten n(e) Anzahl der Kanten

n(f) Anzahl der Facettenn(f) Anzahl der Facetten


Betrachtung von CH als planarer GraphBetrachtung von CH als planarer Graph Jede Facette des entsprechenden Graphen hat 3 Kanten n(e) Jede Facette des entsprechenden Graphen hat 3 Kanten n(e)

(Triangulierung der CH)(Triangulierung der CH) Jede Kante hat liegt an 2 Facetten n(f) Jede Kante hat liegt an 2 Facetten n(f)

2n(e) = 3 n(f)2n(e) = 3 n(f)Einsetzen in Eulerformel :Einsetzen in Eulerformel :

Beispiel: n+n(f)-2 = 3n(f)/2Beispiel: n+n(f)-2 = 3n(f)/2

=> n(f) = 2n-4=> n(f) = 2n-4=> n(e) = 3n-6=> n(e) = 3n-6


Gift-WrappingGift-Wrapping Algorithmus :Algorithmus :

1. Bestimme eine Grenzfläche E der Hülle 1. Bestimme eine Grenzfläche E der Hülle

2. Solange bis entstehende Form geschlossen 2. Solange bis entstehende Form geschlossen

3.3. Biege Fläche E aus der bisher entstandenen Biege Fläche E aus der bisher entstandenen Form Form

um eine ihrer Kanten bis ein Punkt erreicht um eine ihrer Kanten bis ein Punkt erreicht wird.wird.

4.4. Dieser Punkt bildet mit den Eckpunkten der Dieser Punkt bildet mit den Eckpunkten der Kante von Kante von

E eine neue GrenzflächeE eine neue Grenzfläche


Gift-WrappingGift-Wrapping Laufzeit : Laufzeit :

Für jede entstehende Fläche Test mit n PunktenFür jede entstehende Fläche Test mit n Punkten

Für f entstehende Flächen Für f entstehende Flächen

=> O(f* n), im schlimmsten Fall wieder O(n²)=> O(f* n), im schlimmsten Fall wieder O(n²)


Divide-and-ConquerDivide-and-Conquer Algorithmus :Algorithmus :

1. Sortiere Punktemenge nach x-Wert1. Sortiere Punktemenge nach x-Wert

2. Teile Punktmenge rekursiv, bis Mengengröße <=42. Teile Punktmenge rekursiv, bis Mengengröße <=4

3. 3. Füge CH der einzelnen Mengen zusammenFüge CH der einzelnen Mengen zusammen

Zusammenfügen: Zusammenfügen:

1. Suche minimale y-Werte aus beiden Mengen1. Suche minimale y-Werte aus beiden Mengen

2. Analog zu Gift-Wrapping :2. Analog zu Gift-Wrapping :

Biege Fläche mit z-Richtung um die Kante bis man auf einen Biege Fläche mit z-Richtung um die Kante bis man auf einen Punkt trifftPunkt trifft

3. Biege weiter um Kanten der neuen Facette bis CH geschlossen3. Biege weiter um Kanten der neuen Facette bis CH geschlossen


Divide-and-ConquerDivide-and-Conquer Laufzeit :Laufzeit :

Sortieren O(n log n)Sortieren O(n log n)

Zusammenfügen O(n)Zusammenfügen O(n)

O(n log n)O(n log n)

4. Incremental-Algorithmus 4. Incremental-Algorithmus

1. Schrittweise Erklärung des Algorithmus1. Schrittweise Erklärung des Algorithmus

2. Verbesserung durch einen Konfliktgraph2. Verbesserung durch einen Konfliktgraph

3. Pseudocode3. Pseudocode

4.1 Algorithmus4.1 Algorithmus

Im Folgenden repräsentiert CH(r) die KonvexeIm Folgenden repräsentiert CH(r) die KonvexeHülle der 1. r PunkteHülle der 1. r Punkte

Start: Start: Finde 3 Punkte in einer Ebene Finde 3 Punkte in einer Ebene Finde 4. Punkt der nicht in der Ebene liegtFinde 4. Punkt der nicht in der Ebene liegt

Existiert kein 4. Punkt kann eine 2D-AlgorithmusExistiert kein 4. Punkt kann eine 2D-Algorithmusangewandt werdenangewandt werden

Existiert ein 4. Punkt bilden die 4 Ausgangspunkte ein Existiert ein 4. Punkt bilden die 4 Ausgangspunkte ein TetrahedronTetrahedron


Alle Punkte 5 – n werden zufällig gemischtAlle Punkte 5 – n werden zufällig gemischt

nun werden sie nacheinander eingefügtnun werden sie nacheinander eingefügt

Wenn wir Punkt r einfügen können 2 Fälle Wenn wir Punkt r einfügen können 2 Fälle entstehen :entstehen : R liegt in CH(r-1) oder auf der OberflächeR liegt in CH(r-1) oder auf der Oberfläche

=> CH(r) = CH(r-1)=> CH(r) = CH(r-1) r liegt außerhalb von CH(r-1)r liegt außerhalb von CH(r-1)


r liegt außerhalb von CH(r-1) :r liegt außerhalb von CH(r-1) :

Am Punkt r stehend schaut man nach CH(r-1)Am Punkt r stehend schaut man nach CH(r-1) Die Facetten von CH(r-1) teilen sich in :Die Facetten von CH(r-1) teilen sich in :

Nichtsichtbare Facetten – diese bilden weiterhin Nichtsichtbare Facetten – diese bilden weiterhin einen Teil der konvexen Hülleeinen Teil der konvexen Hülle

Sichtbare Facetten – diese gehören nicht mehr zur Sichtbare Facetten – diese gehören nicht mehr zur konvexen Hülle CH(r)konvexen Hülle CH(r)


Unterscheiden können wir diese Facetten Unterscheiden können wir diese Facetten aufgrund des sichtbaren „Horizonts“ von CH(r-1) aufgrund des sichtbaren „Horizonts“ von CH(r-1)

Der Horizont ist wie eine Projektion auf eine Der Horizont ist wie eine Projektion auf eine Ebene von CH(r-1) von p(r) aus zu sehenEbene von CH(r-1) von p(r) aus zu sehen


Die sichtbaren Facetten werden aus CH(r-1) Die sichtbaren Facetten werden aus CH(r-1) entfernt entfernt

Neue Facetten werden eingefügt die p(r) mit den Neue Facetten werden eingefügt die p(r) mit den Kanten des Horizonts von CH(r-1) verbindenKanten des Horizonts von CH(r-1) verbinden

Wir erhalten CH(r)Wir erhalten CH(r)


Problem :Problem :

Möglicherweise liegt p(r) auf einer Facette Möglicherweise liegt p(r) auf einer Facette von CH(r-1) von CH(r-1)

die Facette ist nicht sichtbardie Facette ist nicht sichtbar beim hinzufügen erstellen wir Koplanare beim hinzufügen erstellen wir Koplanare

Facetten Facetten Diese müssen gefunden und Diese müssen gefunden und

zusammengeführt werdenzusammengeführt werden

4.2 Konfliktgraph4.2 Konfliktgraph

Problem : Problem : Wie finden wir die sichtbaren Facetten zu Wie finden wir die sichtbaren Facetten zu

einem Punkt p(r) ?einem Punkt p(r) ? Testen wir jede Facette mit jedem neuen Testen wir jede Facette mit jedem neuen

Punkt finden wir alle sichtbaren in O(n) Punkt finden wir alle sichtbaren in O(n) über n-4 Einfügeschritte über n-4 Einfügeschritte Laufzeit: O(n²)Laufzeit: O(n²)

Wie geht es besser ?Wie geht es besser ?


Der Trick besteht im Vorarbeiten :Der Trick besteht im Vorarbeiten :für jede Facette f von CH(r) erstellen wir einen für jede Facette f von CH(r) erstellen wir einen Menge P-Konflikt(f) mit allen Punkten die f Menge P-Konflikt(f) mit allen Punkten die f sehen könnensehen können

für jeden Punkt p >r erstellen wir die Menge F-für jeden Punkt p >r erstellen wir die Menge F-Konflikt(p) mit allen Facetten die dieser Punkt Konflikt(p) mit allen Facetten die dieser Punkt sehen kann sehen kann


Punkte und Facetten werden in einem bi-partitenPunkte und Facetten werden in einem bi-partitenGraph G gespeichert.Graph G gespeichert.

Konflikt : Konflikt : benachbarte Facetten und Punktebenachbarte Facetten und Punktekönnen nicht gleichzeitig in einer konvexen Hülle existieren können nicht gleichzeitig in einer konvexen Hülle existieren

Wird ein Punkt hinzugefügt => werden dieWird ein Punkt hinzugefügt => werden diebenachbarten Facetten gelöschtbenachbarten Facetten gelöscht


Der Graph G kann in linearer Zeit für CH(4) erstellt Der Graph G kann in linearer Zeit für CH(4) erstellt werdenwerden

wird Punkt r hinzugefügt wird Punkt r hinzugefügt Finden der Konfliktfacetten in G Finden der Konfliktfacetten in G Entfernen der Facetten aus CH(r-1) Entfernen der Facetten aus CH(r-1) Löschen der entsprechenden Facetten aus GLöschen der entsprechenden Facetten aus G Erstellen der neuen Facetten in CH(r) und einfügen dieser Erstellen der neuen Facetten in CH(r) und einfügen dieser

Facetten in GFacetten in G Entscheidender Schritt ist nun das Auffinden der Konfliktpunkte Entscheidender Schritt ist nun das Auffinden der Konfliktpunkte

für die neuen Facetten!für die neuen Facetten!


Wie finden wir die Konfliktpunkte der neuen Wie finden wir die Konfliktpunkte der neuen Facetten ?Facetten ? Angenommen ein Punkt p(t) sieht die neue Facette fAngenommen ein Punkt p(t) sieht die neue Facette f p(t) sieht auch die Kante e von f , e aus dem Horizont p(t) sieht auch die Kante e von f , e aus dem Horizont

CH(r-1)CH(r-1) p(t) sah entweder f1 oder f2 , die Facetten die in CH(r-p(t) sah entweder f1 oder f2 , die Facetten die in CH(r-

1) die Kante e hatten 1) die Kante e hatten

=> Wir finden alle Konfliktpunkte in den Konfliktlisten von => Wir finden alle Konfliktpunkte in den Konfliktlisten von f1 und f2f1 und f2

4.3 Pseudocode4.3 Pseudocode

Eingabe : Eine Menge P von n Punkten Eingabe : Eine Menge P von n Punkten

Ausgabe : Die Konvexe Hülle CH(P) von PAusgabe : Die Konvexe Hülle CH(P) von P

1. Finde die 4 Punkte p1,p2,p3,p4 in P die ein Tetrahedron formen1. Finde die 4 Punkte p1,p2,p3,p4 in P die ein Tetrahedron formen

2. Dieses bildet bereits die konvexe Hülle CH von p1,p2,p3,p42. Dieses bildet bereits die konvexe Hülle CH von p1,p2,p3,p4

3. Erstelle eine zufällige Permutation von p5 bis pn3. Erstelle eine zufällige Permutation von p5 bis pn

4. Initialisiere den Konfliktgraphen G für alle „sichtbaren“ Paare (p(t),f)4. Initialisiere den Konfliktgraphen G für alle „sichtbaren“ Paare (p(t),f)

für alle Facetten f von CH(4) und p(t) aus P mit t>4für alle Facetten f von CH(4) und p(t) aus P mit t>4

5. Für Laufvariable r von 5 bis n5. Für Laufvariable r von 5 bis n

::

::


::


6. Füge p(r) in CH ein6. Füge p(r) in CH ein

7.7. Falls F-Konflikt(p(r)) nicht leer ist Falls F-Konflikt(p(r)) nicht leer ist **p(r) liegt auß. CH****p(r) liegt auß. CH**

8.8. Lösche alle Facetten aus F-Konflikt(p(r)) aus CH Lösche alle Facetten aus F-Konflikt(p(r)) aus CH

9.9. Laufe den Rand der sichtbaren Region ab und erstelle Laufe den Rand der sichtbaren Region ab und erstelle

eine Liste L der Horizontkanten eine Liste L der Horizontkanten

10.10. für alle e aus L für alle e aus L

11.11. verbinde alle e durch ein Dreieck f als neue Facettenverbinde alle e durch ein Dreieck f als neue Facetten

von CH(r) mit p(r)von CH(r) mit p(r)

12. 12. Füge einen Knoten für für f in G ein Füge einen Knoten für für f in G ein

: :


::


::

12. 12. Füge einen Knoten für f in G einFüge einen Knoten für f in G ein

13.13. f1 und f2 seien die an e gelegenen Facetten aus CH f1 und f2 seien die an e gelegenen Facetten aus CH

14.14. Erstelle Liste P(e) aus Konfliktlisten von f1 und f2 Erstelle Liste P(e) aus Konfliktlisten von f1 und f2

15.15. für alle Punkte p aus P(e) für alle Punkte p aus P(e)

16.16. falls f sichtbar von p => füge Kante (p,f) in G hinzu falls f sichtbar von p => füge Kante (p,f) in G hinzu

17.17. Lösche Knoten für p(r) und Facetten aus F-Konflikt(p(r)) aus Lösche Knoten für p(r) und Facetten aus F-Konflikt(p(r)) aus GG

18. 18. Ergebnis : CH(r)Ergebnis : CH(r)

Zurück zu 5. Nach n-4 Schritten erhalten wir CH(P)Zurück zu 5. Nach n-4 Schritten erhalten wir CH(P)

5. Laufzeitanalyse 5. Laufzeitanalyse

Alle Schritte vor der HauptschleifeAlle Schritte vor der Hauptschleife Ausführbar in linearer Zeit Ausführbar in linearer Zeit O(n)O(n)

p(r) innerhalb von CH(r-1)p(r) innerhalb von CH(r-1) F-Konflikt(p(r)) ist leerF-Konflikt(p(r)) ist leer Konstante Zeit Konstante Zeit

p(r) liegt außerhalb von CH(r-1) ?p(r) liegt außerhalb von CH(r-1) ?

5. Laufzeitanalyse5. Laufzeitanalyse

Liegt der Punkt außerhalb von CH(r-1)Liegt der Punkt außerhalb von CH(r-1) Anzahl der Operationen hängt ab von :Anzahl der Operationen hängt ab von :

Menge der zu entfernenden Facetten Menge der zu entfernenden Facetten O(kard(F-Konflikt(p(r))) O(kard(F-Konflikt(p(r))) kard(F-Konflikt(p(r)) = Kardinalität der Mengekard(F-Konflikt(p(r)) = Kardinalität der Menge

Menge der einzufügenden FacettenMenge der einzufügenden Facetten entspricht der Menge von Rand-Kanten des Horizonts von entspricht der Menge von Rand-Kanten des Horizonts von

CH(r-1) von p(r) aus gesehenCH(r-1) von p(r) aus gesehen

Eine Kante kann nur gelöscht werden, wenn sie Eine Kante kann nur gelöscht werden, wenn sie vorher erstellt wurdevorher erstellt wurde

=> Wie viele Kanten erstellt unser Algorithmus ?=> Wie viele Kanten erstellt unser Algorithmus ?

5.Laufzeitanalyse5.Laufzeitanalyse

Satz : Die zu erwartende Anzahl von erstellten Facetten Satz : Die zu erwartende Anzahl von erstellten Facetten für die CH ist höchstens 6n-20für die CH ist höchstens 6n-20

Die Anzahl der Kanten ist höchstens 3r-6 (siehe 3.)Die Anzahl der Kanten ist höchstens 3r-6 (siehe 3.) Grad(p(r)) = deg(p(r),CH(p(r))) Anzahl der Facetten die beim Grad(p(r)) = deg(p(r),CH(p(r))) Anzahl der Facetten die beim

einfügen von p(r) erstellt werden = Facetten die an p(r) einfügen von p(r) erstellt werden = Facetten die an p(r) angrenzenangrenzen

Die Summe über die Grade der Punkte nach Euler <= 6r-12Die Summe über die Grade der Punkte nach Euler <= 6r-12 Über r eingefügte Punkte ist der Grad eines Punktes <= 6-12/rÜber r eingefügte Punkte ist der Grad eines Punktes <= 6-12/r Vorsicht : Punkte 1-4 sind bereits eingefügt Vorsicht : Punkte 1-4 sind bereits eingefügt

Summe (Grad p1,…,p4) ist 12Summe (Grad p1,…,p4) ist 12

Somit ist der zu erwartende Durchschnittswert von Somit ist der zu erwartende Durchschnittswert von deg(p(r),CH(p(r))) :deg(p(r),CH(p(r))) :


4 Startfacetten + zu erwartende Anzahl zu erstellender Facetten in r 4 Startfacetten + zu erwartende Anzahl zu erstellender Facetten in r SchrittenSchritten


Facette nur löschbar wenn sie erstellt wurde &Facette nur löschbar wenn sie erstellt wurde &

Anzahl erstellter Facetten in O(n)Anzahl erstellter Facetten in O(n)

Was bleibt ?Was bleibt ? Erstellen der Konfliktliste für neue Facetten fErstellen der Konfliktliste für neue Facetten f Löschen der entfernten Facetten und des eingefügten Punktes Löschen der entfernten Facetten und des eingefügten Punktes

aus dem Graphen => lineare Zeit in Anzahl der Knotenaus dem Graphen => lineare Zeit in Anzahl der KnotenJeder Knoten kann nur einmal eingefügt und entfernt werdenJeder Knoten kann nur einmal eingefügt und entfernt werden


Was kostet uns das Finden der Konflikte ?Was kostet uns das Finden der Konflikte ? Zeilen 14-16 :Zeilen 14-16 :

Erstellen von P(e) für jede Randkante des HorizontsErstellen von P(e) für jede Randkante des Horizonts

Finden der Konflikte für an e angefügte FacetteFinden der Konflikte für an e angefügte Facette O(card(P(e))O(card(P(e))

Wir benötigen somit :Wir benötigen somit :

Mithilfe eines Lemmas der Delaunay-Triangulation lässt sich Mithilfe eines Lemmas der Delaunay-Triangulation lässt sich zeigen :zeigen :


Laufzeitanalyse ergibt:Laufzeitanalyse ergibt:

O(n log n)O(n log n)

Anschauliche Konvexe Hülle im 3D:Anschauliche Konvexe Hülle im 3D:

http://www.voronoi3d.com/testing/voronoi3d.htmlhttp://www.voronoi3d.com/testing/voronoi3d.html

AusblickAusblick

Voronoi-Diagramme, Delauny-Triangulation, Konvexe Voronoi-Diagramme, Delauny-Triangulation, Konvexe HülleHülle

Weblink: Weblink: http://www.pi6.fernuni-hagen.de/GeommLab/Voroglidehttp://www.pi6.fernuni-hagen.de/GeommLab/Voroglide

QuellenQuellen

Buchquellen :Buchquellen : Computational Geometrie Computational Geometrie de Berg, van Krefeld, de Berg, van Krefeld,

Overmars, Schwarzkopf Overmars, Schwarzkopf

ISBN: 3-540-65620-0ISBN: 3-540-65620-0

Internetquellen :Internetquellen : http://www2.in.tu-clausthal.de/~hormann/teaching/ProSemWS04/PS.AlGeo.07.12http://www2.in.tu-clausthal.de/~hormann/teaching/ProSemWS04/PS.AlGeo.07.12

.2004.b.pdf.2004.b.pdf

Konvexe Hüllen TU ClausthalKonvexe Hüllen TU Clausthal http://www.ikg.uni-hannover.de/lehre/katalog/alg_geom/v5_Punkthuellen.pdfhttp://www.ikg.uni-hannover.de/lehre/katalog/alg_geom/v5_Punkthuellen.pdf

Punkthüllen Universität HannoverPunkthüllen Universität Hannover http://www.inf.fh-flensburg.de/lang/algorithmen/geo/index.htmhttp://www.inf.fh-flensburg.de/lang/algorithmen/geo/index.htm

Konvexe Hülle Fachhochschule FlensburgKonvexe Hülle Fachhochschule Flensburg

EndeEnde

Vielen Dank für ihre AufmerksamkeitVielen Dank für ihre Aufmerksamkeit

Documents

Seminar Computational Geometry Convex Hull