Delaunay-Triangulation

In der algorithmischen Geometrie unterteilt eine Delaunay- oder Delone-Triangulierung einer Punktmenge in der Ebene deren konvexe Hülle ^{[ 1 ]} in Dreiecke, deren Umkreise keine der Punkte enthalten; das heißt, jeder Umkreis hat seine Erzeugerpunkte auf seinem Umfang, aber alle anderen Punkte der Menge liegen außerhalb davon. Dadurch wird die Größe des kleinsten Winkels in jedem der Dreiecke maximiert und die Bildung von schmalen Dreiecken vermieden .

Die Triangulation ist nach Boris Delaunay benannt , der sich seit 1934 damit befasst. ^{[ 2 ]}

Liegen alle Punkte auf einer Geraden, so ist der Begriff der Triangulierung nicht mehr anwendbar, und es existiert keine Delaunay-Triangulierung. Für vier oder mehr Punkte auf demselben Kreis (z. B. die Eckpunkte eines Rechtecks) ist die Delaunay-Triangulierung nicht eindeutig: Jede der beiden möglichen Triangulierungen, die das Viereck in zwei Dreiecke zerlegen, erfüllt die „Delaunay-Bedingung“, d. h. die Forderung, dass die Umkreise aller Dreiecke leer sind.

Durch die Betrachtung umschriebener Sphären lässt sich der Begriff der Delaunay-Triangulierung auf drei und höhere Dimensionen erweitern. Verallgemeinerungen sind auch auf andere Metriken als die euklidische Distanz möglich . In diesen Fällen ist die Existenz oder Eindeutigkeit einer Delaunay-Triangulierung jedoch nicht garantiert.

Beziehung zum Voronoi-Diagramm

Die Delaunay-Triangulation mit allen Umkreisen und ihren Mittelpunkten (rot).

Verbindet man die Mittelpunkte der Umkreise, entsteht das Voronoi-Diagramm (rot).

Die Delaunay- Triangulierung einer diskreten Punktmenge $P$ in allgemeiner Lage entspricht dem dualen Graphen des Voronoi-Diagramms von $P.$ Die Umkreismittelpunkte der Delaunay-Dreiecke sind die Knotenpunkte des Voronoi-Diagramms. Im zweidimensionalen Fall sind die Knotenpunkte des Voronoi-Diagramms durch Kanten verbunden, die sich aus den Nachbarschaftsbeziehungen der Delaunay-Dreiecke ableiten lassen: Wenn zwei Dreiecke in der Delaunay-Triangulierung eine Kante gemeinsam haben, werden ihre Umkreismittelpunkte mit einer Kante in der Voronoi-Tessellation verbunden.

Sonderfälle, in denen diese Beziehung nicht besteht oder mehrdeutig ist, umfassen beispielsweise folgende Fälle:

Drei oder mehr kollineare Punkte, deren Umkreise unendliche Radien haben .
Vier oder mehr Punkte auf einem perfekten Kreis, wobei die Triangulierung mehrdeutig ist und alle Umkreismittelpunkte trivialerweise identisch sind. In diesem Fall enthält das Voronoi-Diagramm Knoten vom Grad vier oder höher, und sein dualer Graph enthält polygonale Flächen mit vier oder mehr Seiten. Die verschiedenen Triangulierungen dieser Flächen vervollständigen die verschiedenen möglichen Delaunay-Triangulierungen.
$Im Fall einer endlichen Menge P$ sind die ins Unendliche verlaufenden Kanten des Voronoi-Diagramms durch diese Relation nicht definiert . Wird die Delaunay- Triangulierung mithilfe des Bowyer-Watson-Algorithmus berechnet, sind die Umkreismittelpunkte der Dreiecke, die einen gemeinsamen Eckpunkt mit dem „Super“-Dreieck haben, zu ignorieren. Ins Unendliche verlaufende Kanten beginnen in einem Umkreismittelpunkt und stehen senkrecht auf der gemeinsamen Kante zwischen dem beibehaltenen und dem ignorierten Dreieck.

d -dimensionaler Delaunay

Für eine Punktmenge $P$ im ( $d-$ dimensionalen) euklidischen Raum ist eine Delaunay-Triangulierung eine Triangulierung $DT(P),$ sodass kein Punkt in $P$ innerhalb der Umkreishypersphäre eines $d$ - Simplex in $DT(P)$ liegt . Es ist bekannt ^{[ 2 ]} $, dass genau eine Delaunay-Triangulierung für P$ existiert, wenn $P$ eine Punktmenge in allgemeiner Lage ist ; das heißt, die affine Hülle von $P$ ist $d-$ dimensional, und keine Menge von $d + 2$ Punkten in $P liegt auf dem Rand einer Kugel, deren Inneres$ $P$ nicht schneidet .

Das Problem der Bestimmung der Delaunay-Triangulierung einer Punktmenge im $d-$ dimensionalen euklidischen Raum lässt sich auf die Bestimmung der konvexen Hülle einer Punktmenge im ( $d +1$ )-dimensionalen Raum zurückführen. Dies geschieht, indem man jedem Punkt $p$ eine zusätzliche Koordinate gleich $| p | ²$ zuweist und ihn so in ein Hyperparaboloid verwandelt (dies wird als „Anheben“ bezeichnet). Anschließend betrachtet man die Unterseite der konvexen Hülle (da die obere Endkappe vom Ursprung weg nach oben zeigt und verworfen werden muss) und bildet durch Entfernen der letzten Koordinate zurück in $den d$ -dimensionalen Raum ab. Da die konvexe Hülle eindeutig ist, ist auch die Triangulierung eindeutig, vorausgesetzt, alle Facetten der konvexen Hülle sind Simplizes . Nicht-simpliziale Facetten treten nur dann auf, wenn $d +2$ der ursprünglichen Punkte auf derselben $d$ - Hypersphäre liegen , d. h., die Punkte nicht in allgemeiner Lage sind. ^{[ 3 ]}

Eigenschaften

Sei $n$ die Anzahl der Punkte und $d$ die Anzahl der Dimensionen.

Die Vereinigung aller Simplizes in der Triangulierung ist die konvexe Hülle der Punkte.
Die Delaunay-Triangulierung enthält ⁠ ⁠ $\textstyle O{\bigl (}n^{\lceil d/2\rceil }{\bigr )}$ Simplizes. ^{[ 4 ]}
In der Ebene ( $d = 2 ) gibt es, wenn$ $b$ Eckpunkte auf der konvexen Hülle liegen , jede Triangulierung der Punkte höchstens $2 n - 2 - b$ Dreiecke plus eine Außenfläche (siehe Euler-Charakteristik ).
Sind die Punkte gemäß einem Poisson-Prozess mit konstanter Intensität in der Ebene verteilt, so hat jeder Knoten im Durchschnitt sechs umgebende Dreiecke. Allgemeiner gilt für denselben Prozess in $d$ Dimensionen, dass die durchschnittliche Anzahl der Nachbarn eine Konstante ist, die nur von $d$ abhängt . ^{[ 5 ]}
In der Ebene maximiert die Delaunay-Triangulierung den kleinsten Winkel. Im Vergleich zu jeder anderen Triangulierung der Punkte ist der kleinste Winkel in der Delaunay-Triangulierung mindestens so groß wie der kleinste Winkel in jeder anderen. Die Delaunay-Triangulierung minimiert jedoch nicht notwendigerweise den maximalen Winkel. ^{[ 6 ]} Die Delaunay-Triangulierung minimiert auch nicht notwendigerweise die Kantenlänge.
Ein Kreis, der ein beliebiges Delaunay-Dreieck umschreibt, enthält keine weiteren Eingabepunkte in seinem Inneren.
Wenn ein Kreis, der durch zwei der Eingabepunkte verläuft, keine weiteren Eingabepunkte in seinem Inneren enthält, dann ist die Strecke, die die beiden Punkte verbindet, eine Kante einer Delaunay-Triangulierung der gegebenen Punkte.
Jedes Dreieck der Delaunay-Triangulierung einer Punktmenge in $d-$ dimensionalen Räumen entspricht einer Facette der konvexen Hülle der Projektion der Punkte auf ein ( $d + 1$ )-dimensionales Paraboloid , und umgekehrt.
Der nächste Nachbar $b$ zu einem beliebigen Punkt $p$ liegt auf einer Kante $bp$ in der Delaunay-Triangulierung, da der Nächste-Nachbar-Graph ein Teilgraph der Delaunay-Triangulierung ist.
Die Delaunay-Triangulierung ist ein geometrischer Spanner : In der Ebene ( $d = 2$ ) ist der kürzeste Weg zwischen zwei Knoten entlang der Delaunay-Kanten bekanntermaßen nicht länger als das 1,998-fache der euklidischen Distanz zwischen ihnen. ^{[ 7 ]}

Visuelle Delaunay-Definition: Spiegeln

Aus den oben genannten Eigenschaften ergibt sich eine wichtige Erkenntnis: Betrachtet man zwei Dreiecke $△ ABD, △ BCD$ mit der gemeinsamen Kante $BD$ (siehe Abbildungen), so erfüllen die Dreiecke die Delaunay-Bedingung, wenn die Winkelsumme $α + γ \leq 180° ist$ .

Dies ist eine wichtige Eigenschaft, da sie die Anwendung einer Umkehrtechnik ermöglicht . Wenn zwei Dreiecke die Delaunay-Bedingung nicht erfüllen, führt das Vertauschen der gemeinsamen Kante $BD$ mit der gemeinsamen Kante $AC$ zu zwei Dreiecken, die die Delaunay-Bedingung erfüllen:

Diese Triangulierung erfüllt nicht die Delaunay-Bedingung (die Summe von $α$ und $γ$ ist größer als 180°).
Dieses Dreieckspaar erfüllt die Delaunay-Bedingung nicht (es gibt einen Punkt innerhalb des Inneren des Umkreises).
Durch Umkehren der gemeinsamen Kante erhält man eine gültige Delaunay-Triangulierung für die vier Punkte.

Diese Operation wird als Spiegelung bezeichnet und kann auf drei und höhere Dimensionen verallgemeinert werden. ^{[ 8 ]}

Algorithmen

Viele Algorithmen zur Berechnung von Delaunay-Triangulierungen basieren auf schnellen Operationen zur Erkennung, ob ein Punkt innerhalb des Umkreises eines Dreiecks liegt, und einer effizienten Datenstruktur zur Speicherung von Dreiecken und Kanten. In zwei Dimensionen kann man beispielsweise feststellen, ob Punkt $D innerhalb des Umkreises von$ $A, B, C$ liegt , indem man die Determinante berechnet : ^{[ 9 ]}

{\begin{aligned}&{\begin{vmatrix}A_{x}&A_{y}&A_{x}^{2}+A_{y}^{2}&1\\B_{x}&B_{y}&B_{x}^{2}+B_{y}^{2}&1\\C_{ x}&C_{y}&C_{x}^{2}+C_{y}^{2}&1\\D_{x}&D_{y}&D_{x}^{2}+D_{y}^{2}&1\end{vmatrix}}\\[8pt]={}&{\begin{vmatrix} A_{x}-D_{x}&A_{y}-D_{y}&(A_{x}-D_{x})^{2}+(A_{y}-D_{y})^{2}\\B_{x}-D_{x}&B_{y}-D_{y}&(B_{x}-D_{x})^{2}+(B_{y}-D_{y})^{2}\\C_{x}-D_{x}&C_{y}-D_{y}&(C_{x}-D_{x})^{2}+(C_{y}-D_{y})^{2}\end{vmatrix}}>0\end{aligned}}

Wenn $A, B, C gegen den$ Uhrzeigersinn sortiert werden , ist diese Determinante nur dann positiv, wenn $D$ innerhalb des Umkreises liegt.

Flip-Algorithmen

Wie bereits erwähnt, kann man, falls ein Dreieck nicht-Delaunay ist, eine seiner Kanten umkehren. Dies führt zu einem einfachen Algorithmus: Man konstruiert eine beliebige Triangulierung der Punkte und kehrt dann die Kanten um, bis kein Dreieck mehr nicht-Delaunay ist. Leider kann dies Ω(n²) Kantenumkehrungen erfordern $.$ $[10]$ Obwohl ^{sich dieser Algorithmus} auf drei und höhere Dimensionen verallgemeinern lässt, ist seine Konvergenz in diesen Fällen nicht garantiert, da sie von der Zusammenhangseigenschaft des zugrunde liegenden Umkehrgraphen abhängt : Dieser Graph ist für zweidimensionale Punktmengen zusammenhängend, kann aber in höheren Dimensionen unzusammenhängend sein. ^{[ 8 ]}

Inkrementell

Die einfachste und effizienteste Methode zur Berechnung der Delaunay-Triangulierung besteht darin, wiederholt jeweils einen Knoten hinzuzufügen und die betroffenen Teile des Graphen neu zu triangulieren. Beim Hinzufügen eines Knotens $v wird das Dreieck, das$ $v$ enthält, in drei Teile geteilt und anschließend der Flip-Algorithmus angewendet. Naiv umgesetzt, benötigt dies $O(n)$ Zeit: Es werden alle Dreiecke durchsucht, um dasjenige zu finden, das v enthält $,$ $und$ anschließend gegebenenfalls alle Dreiecke weggespiegelt. Die Gesamtlaufzeit beträgt somit $O(n²)$ .

Fügt man die Eckpunkte in zufälliger Reihenfolge ein, so zeigt ein etwas komplizierter Beweis, dass jede Einfügung im Durchschnitt nur $O(1)$ Dreiecke umklappt – obwohl manchmal deutlich mehr umklappt. ^{[ 11 ]} Die Zeit für die Punktlokalisierung ist also noch verbesserungsbedürftig. Wir können die Historie der durchgeführten Aufteilungen und Umklappvorgänge speichern: Jedes Dreieck speichert einen Zeiger auf die zwei oder drei Dreiecke, die es ersetzt haben. Um das Dreieck zu finden, das $v$ enthält , beginnen wir bei einem Wurzeldreieck und folgen dem Zeiger auf ein Dreieck, das $v$ enthält , bis wir ein Dreieck finden, das noch nicht ersetzt wurde. Im Durchschnitt benötigt dies ebenfalls $O(log n)$ Zeit. Über alle Eckpunkte hinweg beträgt die Laufzeit somit $O(n log n)$ . ^{[ 12 ] Obwohl sich die Technik auf höhere Dimensionen erweitern lässt (wie Edelsbrunner und Shah}^{[ 13 ]} bewiesen haben ), kann die Laufzeit exponentiell mit der Dimension wachsen, selbst wenn die finale Delaunay-Triangulierung klein ist.

Der Bowyer-Watson-Algorithmus bietet einen weiteren Ansatz für die inkrementelle Konstruktion. Er stellt eine Alternative zum Kantenumklappen für die Berechnung der Delaunay-Dreiecke dar, die einen neu eingefügten Knoten enthalten.

Leider lassen sich auf Umdrehungen basierende Algorithmen im Allgemeinen schwer parallelisieren, da das Hinzufügen eines bestimmten Punktes (z. B. des Mittelpunkts eines Wagenrades) zu bis zu $O(n)$ aufeinanderfolgenden Umdrehungen führen kann. Blelloch et al. ^{[ 14 ]} schlugen eine weitere Version eines inkrementellen Algorithmus auf Basis des Rip-and-Tent-Verfahrens vor, der praktisch und mit polylogarithmischem Spann hochgradig parallelisierbar ist .

Teile und herrsche

Ein Divide-and-Conquer-Algorithmus für Triangulierungen in zwei Dimensionen wurde von Lee und Schachter entwickelt und von Guibas und Stolfi ^{[ 9 ]}^{[ 15 ]} sowie später von Dwyer ^{[ 16 ]} verbessert. In diesem Algorithmus wird rekursiv eine Linie gezeichnet, um die Knoten in zwei Mengen zu teilen. Für jede Menge wird die Delaunay-Triangulierung berechnet, und anschließend werden die beiden Mengen entlang der Trennlinie zusammengeführt. Durch geschickte Tricks kann die Zusammenführung in $O(n)$ Zeit durchgeführt werden , sodass die Gesamtlaufzeit $O(n log n)$ beträgt . ^{[ 17 ]}

Bei bestimmten Arten von Punktmengen, wie z. B. einer gleichmäßigen Zufallsverteilung, kann durch intelligentes Auswählen der Trennlinien die erwartete Zeit auf $O(n log log n)$ reduziert werden , wobei die Worst-Case-Performance erhalten bleibt.

Ein Divide-and-Conquer-Paradigma zur Durchführung einer Triangulierung in $d$ Dimensionen wird in „DeWall: A fast divide and contrar Delaunay triangulation algorithm in E ^d “ von P. Cignoni, C. Montani, R. Scopigno vorgestellt. ^{[ 18 ]}

Der Divide-and-Conquer-Algorithmus hat sich als die sequenziell schnellste Technik zur DT-Generierung erwiesen. ^{[ 19 ]}^{[ 20 ]}

Sweephull

Sweephull ^{[ 21 ]} ist eine Hybridtechnik zur 2D-Delaunay-Triangulierung, die eine radial propagierende Sweep-Hull-Funktion und einen Flipping-Algorithmus verwendet. Die Sweep-Hull-Funktion wird sequenziell erstellt, indem eine radial sortierte Menge von 2D-Punkten iterativ durchlaufen und Dreiecke mit dem sichtbaren Teil der konvexen Hülle verbunden werden. Dadurch entsteht eine nicht überlappende Triangulierung. Eine konvexe Hülle kann auf diese Weise konstruiert werden, solange die Reihenfolge der Punkte sicherstellt, dass kein Punkt innerhalb des Dreiecks liegt. Die radiale Sortierung sollte jedoch das Flipping minimieren, indem sie von Anfang an eine hohe Delaunay-Eigenschaft aufweist. Dies wird dann mit einem abschließenden iterativen Dreieck-Flipping-Schritt kombiniert.

Anwendungen

Der euklidische minimale Spannbaum einer Punktmenge ist eine Teilmenge der Delaunay-Triangulierung derselben Punkte, ^{[ 22 ]} und dies kann zur effizienten Berechnung genutzt werden.

Für die Modellierung von Gelände oder anderen Objekten anhand einer Punktwolke liefert die Delaunay-Triangulierung eine geeignete Menge von Dreiecken, die als Polygone im Modell verwendet werden können. Insbesondere vermeidet die Delaunay-Triangulierung schmale Dreiecke (da diese im Verhältnis zu ihrer Fläche große Umkreise aufweisen). Siehe trianguliertes unregelmäßiges Netzwerk .

Delaunay-Triangulierungen können verwendet werden, um die Dichte oder Intensität von Punktabtastungen mittels des Delaunay-Tessellationsfeldschätzers (DTFE) zu bestimmen .

Delaunay-Triangulierungen werden aufgrund der Winkelgarantie und der Entwicklung schneller Triangulierungsalgorithmen häufig zur Netzgenerierung für raumdiskretisierte Löser wie die Finite-Elemente-Methode und die Finite-Volumen-Methode in der Physiksimulation verwendet. Typischerweise wird das zu vernetzende Gebiet als grober simplizialer Komplex spezifiziert ; für ein numerisch stabiles Netz muss es verfeinert werden, beispielsweise mithilfe des Ruppert-Algorithmus .

Die zunehmende Beliebtheit von Finite-Elemente-Methoden (FEM) und Randelementmethoden (BEM ) verstärkt den Anreiz zur Verbesserung automatischer Vernetzungsalgorithmen. Allerdings können all diese Algorithmen verzerrte und sogar unbrauchbare Netzelemente erzeugen. Glücklicherweise existieren verschiedene Verfahren, mit denen sich die Qualität eines bestehenden Netzes verbessern lässt. Ein Beispiel hierfür ist die Glättung (auch Netzverfeinerung genannt), bei der Knoten neu positioniert werden, um Elementverzerrungen zu minimieren. Die Methode des gestreckten Netzes ermöglicht die einfache und schnelle Generierung pseudoregulärer Netze, die die Delaunay-Kriterien erfüllen, in einem einzigen Lösungsschritt.

Die eingeschränkte Delaunay-Triangulation findet Anwendung in der Pfadplanung beim automatisierten Fahren und in der topografischen Vermessung. ^{[ 23 ]}

Siehe auch

Beta-Skelett
Zentroidale Voronoi-Tessellation
Algorithmen für konvexe Hüllen
Delaunay-Verfeinerung
Delone-Satz – auch bekannt als Delaunay-Satz
Ungeordnete Hyperuniformität
Traversierung vom entferntesten Ausgangspunkt – inkrementelle Voronoi-Einfügung
Gabriel-Graph
Gradientenmusteranalyse
Hamming-Schranke – Kugelpackungsschranke
Linde-Buzo-Gray-Algorithmus
Lloyd-Algorithmus – Voronoi-Iteration
Meyer-Set
Pisot–Vijayaraghavan-Nummer
Pitteway-Triangulation
Plesioeder
Quasikristall
Quasitriangulation
Salem-Nummer
Steiner-Punkt (Dreieck)
Dreiecksnetz
Urquhart-Diagramm
Voronoi-Diagramm

Referenzen

^ Grob gesagt, der Bereich, den ein um die Punkte gespanntes Gummiband umschließen würde.
^ ^Delaunay , Boris ( ¹⁹³⁴ ). „Sur la sphère vide“ [Über die leere Kugel]. Bulletin de l'Académie des Sciences de l'URSS, Classe des Sciences Mathématiques et Naturelles (auf Französisch). 6 : 793–800 .
^ Fukuda, Komei . „Häufig gestellte Fragen zur Polyederberechnung“ . www.cs.mcgill.ca . Abgerufen am 29. Oktober 2018 .
^ Seidel, Raimund (1995). „Der obere Schrankensatz für Polytope: ein einfacher Beweis seiner asymptotischen Version“. Computational Geometry . 5 (2): 115–116 . doi : 10.1016/0925-7721(95)00013-Y .
^ Meijering, JL (1953). „Grenzflächen, Kantenlänge und Anzahl der Eckpunkte in Kristallaggregaten mit zufälliger Keimbildung“ (PDF) . Philips Research Reports . 8 : 270–290 . Archiviert vom Original (PDF) am 08.03.2017.Wie von Dwyer, Rex A. (1991) zitiert. „Höherdimensionale Voronoĭ-Diagramme in linearer erwarteter Zeit“. Discrete and Computational Geometry . 6 (4): 343–367 . doi : 10.1007/BF02574694 . MR 1098813 .
^ Edelsbrunner, Herbert ; Tan, ^Tiow Seng; Waupotitsch, Roman (1992). „Ein O ( n² log n )-Zeitalgorithmus für die Minimax-Winkeltriangulation“ (PDF) . SIAM Journal on Scientific and Statistical Computing . 13 (4): 994–1008 . CiteSeerX 10.1.1.66.2895 . doi : 10.1137 /0913058 . MR 1166172. Archiviert vom Original (PDF) am 9. Februar 2017. Abgerufen am 24. Oktober 2017 . Die
^ Xia, Ge (2013) . „Der Streckungsfaktor der Delaunay-Triangulierung ist kleiner als 1,998“. SIAM Journal on Computing . 42 (4): 1620–1659 . arXiv : 1103.4361 . doi : 10.1137/110832458 . MR 3082502. S2CID 6646528 .
^ ^a ^b De Loera, Jesús A. ; Rambau, Jörg; Santos, Francisco (2010). Triangulationen, Strukturen für Algorithmen und Anwendungen . Algorithmen und Berechnung in der Mathematik. Band 25. Springer.
^ ^a ^b Guibas, Leonidas ; Stolfi, Jorge (1985). „Primitives for the manipulation of general subdivisions and the computation of Voronoi“ . ACM Transactions on Graphics . 4 (2): 74–123 . doi : 10.1145/282918.282923 . S2CID 52852815 .
^ Hurtado, F. ; Noy, M.; Urrutia, J. (1999). „Flipping Edges in Triangulations“ . Discrete & Computational Geometry . 22 (3): 333–346 . doi : 10.1007/PL00009464 .
^ Guibas, Leonidas J .; Knuth, Donald E .; Sharir, Micha (1992). „Randomisierte inkrementelle Konstruktion von Delaunay- und Voronoi-Diagrammen“. Algorithmica . 7 ( 1–6 ): 381–413 . doi : 10.1007/BF01758770 . S2CID 3770886 .
^ de Berg, Mark; Otfried Cheong ; Marc van Kreveld; Mark Overmars (2008). Computergeometrie: Algorithmen und Anwendungen (PDF) . Springer-Verlag. ISBN 978-3-540-77973-5Archiviert vom Original (PDF) am 28.10.2009 . Abgerufen am 23.02.2010 .
^ Edelsbrunner, Herbert ; Shah, Nimish (1996). „Inkrementelles topologisches Umklappen funktioniert für reguläre Triangulierungen“. Algorithmica . 15 (3): 223–241 . doi : 10.1007/BF01975867 . S2CID 12976796 .
^ Blelloch, Guy; Gu, Yan; Shun, Julian; und Sun, Yihan. Parallelismus in randomisierten inkrementellen Algorithmen. Archiviert am 25.04.2018 in der Wayback Machine . SPAA 2016. doi:10.1145/2935764.2935766.
^ Peterson, Samuel. „Berechnung eingeschränkter Delaunay-Triangulationen in der Ebene“ . www.geom.uiuc.edu . Archiviert vom Original am 22. September 2017. Abgerufen am 25. April 2018 .
^ Dwyer, Rex A. (November 1987). „Ein schnellerer Divide-and-Conquer-Algorithmus zur Konstruktion von Delaunay-Triangulierungen“. Algorithmica . 2 ( 1–4 ): 137–151 . doi : 10.1007/BF01840356 . S2CID 10828441 .
^ Leach, G. (Juni 1992). „Verbesserung von Delaunay-Triangulationsalgorithmen im ungünstigsten Fall“. 4. Kanadische Konferenz für Computergeometrie . CiteSeerX 10.1.1.56.2323 .
^ Cignoni, P.; C. Montani; R. Scopigno (1998). „DeWall: Ein schneller Divide-and-Conquer-Delaunay-Triangulationsalgorithmus in E ^d “. Computer-Aided Design . 30 (5): 333–341 . doi : 10.1016/S0010-4485(97)00082-1 .
^ Ein Vergleich sequentieller Delaunay-Triangulationsalgorithmen „Archivierte Kopie“ (PDF) . Archiviert vom Original (PDF) am 08.03.2012 . Abgerufen am 18.08.2010 .{{cite web}}: CS1 Wartung: Archivierte Kopie als Titel ( Link )
^ „Triangulationsalgorithmen und Datenstrukturen“ . www.cs.cmu.edu . Archiviert vom Original am 10. Oktober 2017. Abgerufen am 25. April 2018 .
^ „S-hull“ (PDF) . s-hull.org . Archiviert (PDF) vom Original am 27.10.2013 . Abgerufen am 25. April 2018 .
^ Franz Aurenhammer; Rolf Klein; Der-tsai Lee (26. Juni 2013). Voronoi-Diagramme und Delaunay-Triangulationen . World Scientific Publishing Company. S. 197–. ISBN 978-981-4447-65-2Die
^ Sterling J. Anderson, Sisir B. Karumanchi, Karl Iagnemma (5. Juli 2012). „Constraint-based planning and control for safe, semi-autonomous operation of vehicles“ (PDF) . 2012 IEEE Intelligent Vehicles Symposium . IEEE. doi : 10.1109/IVS.2012.6232153 . Archiviert vom Original (PDF) am 28. Februar 2019. Abgerufen am 27. Februar 2019 .

Externe Links

Henry, Ian (11. Juli 2022). „ Visualisierung der Delaunay-Triangulation “. Blogbeitrag mit detaillierten Algorithmen zur Delaunay-Triangulation.
Delaunay-Triangulierung in CGAL , der Bibliothek für Algorithmen der Computergeometrie:
- Mariette Yvinec . 2D-Triangulation . Abgerufen im April 2010.
- Pion, Sylvain; Teillaud, Monique . 3D-Triangulationen . Abgerufen im April 2010.
- Hornus, Samuel; Devillers, Olivier; Jamin, Clément. dD-Triangulationen .
- Hert, Susan; Seel, Michael. dD Konvexe Hüllen und Delaunay-Triangulationen . Abgerufen im April 2010.
„ Poly2Tri: Inkrementelle eingeschränkte Delaunay-Triangulierung . Open-Source-C++-Implementierung. Abgerufen im April 2019.“
„ Divide & Conquer Delaunay-Triangulationskonstruktion “. Open-Source-C99-Implementierung. Abgerufen im April 2019.
„ CDT: Constrained Delaunay Triangulation in C++ “. Open-Source-C++-Implementierung. Abgerufen im August 2022.

[1] Grob gesagt, der Bereich, den ein um die Punkte gespanntes Gummiband umschließen würde.

[Delaunay1934-2] Delaunay , Boris ( ¹⁹³⁴ ). „Sur la sphère vide“ [Über die leere Kugel]. Bulletin de l'Académie des Sciences de l'URSS, Classe des Sciences Mathématiques et Naturelles (auf Französisch). 6 : 793–800 .

[Fukuda-3] Fukuda, Komei . „Häufig gestellte Fragen zur Polyederberechnung“ . www.cs.mcgill.ca . Abgerufen am 29. Oktober 2018 .

[Seidel1995-4] Seidel, Raimund (1995). „Der obere Schrankensatz für Polytope: ein einfacher Beweis seiner asymptotischen Version“. Computational Geometry . 5 (2): 115–116 . doi : 10.1016/0925-7721(95)00013-Y .

[Meijering-5] Meijering, JL (1953). „Grenzflächen, Kantenlänge und Anzahl der Eckpunkte in Kristallaggregaten mit zufälliger Keimbildung“ (PDF) . Philips Research Reports . 8 : 270–290 . Archiviert vom Original (PDF) am 08.03.2017.Wie von Dwyer, Rex A. (1991) zitiert. „Höherdimensionale Voronoĭ-Diagramme in linearer erwarteter Zeit“. Discrete and Computational Geometry . 6 (4): 343–367 . doi : 10.1007/BF02574694 . MR 1098813 .

[ETW1992-6] Edelsbrunner, Herbert ; Tan, ^Tiow Seng; Waupotitsch, Roman (1992). „Ein O ( n² log n )-Zeitalgorithmus für die Minimax-Winkeltriangulation“ (PDF) . SIAM Journal on Scientific and Statistical Computing . 13 (4): 994–1008 . CiteSeerX 10.1.1.66.2895 . doi : 10.1137 /0913058 . MR 1166172. Archiviert vom Original (PDF) am 9. Februar 2017. Abgerufen am 24. Oktober 2017 . Die

[Xia-7] Xia, Ge (2013) . „Der Streckungsfaktor der Delaunay-Triangulierung ist kleiner als 1,998“. SIAM Journal on Computing . 42 (4): 1620–1659 . arXiv : 1103.4361 . doi : 10.1137/110832458 . MR 3082502. S2CID 6646528 .

[DRS-8] De Loera, Jesús A. ; Rambau, Jörg; Santos, Francisco (2010). Triangulationen, Strukturen für Algorithmen und Anwendungen . Algorithmen und Berechnung in der Mathematik. Band 25. Springer.

[GS1985-9] Guibas, Leonidas ; Stolfi, Jorge (1985). „Primitives for the manipulation of general subdivisions and the computation of Voronoi“ . ACM Transactions on Graphics . 4 (2): 74–123 . doi : 10.1145/282918.282923 . S2CID 52852815 .

[Hurtado-10] Hurtado, F. ; Noy, M.; Urrutia, J. (1999). „Flipping Edges in Triangulations“ . Discrete & Computational Geometry . 22 (3): 333–346 . doi : 10.1007/PL00009464 .

[GKS1992-11] Guibas, Leonidas J .; Knuth, Donald E .; Sharir, Micha (1992). „Randomisierte inkrementelle Konstruktion von Delaunay- und Voronoi-Diagrammen“. Algorithmica . 7 ( 1–6 ): 381–413 . doi : 10.1007/BF01758770 . S2CID 3770886 .

[deBerg-12] Berg, Mark; Otfried Cheong ; Marc van Kreveld; Mark Overmars (2008). Computergeometrie: Algorithmen und Anwendungen (PDF) . Springer-Verlag. ISBN 978-3-540-77973-5Archiviert vom Original (PDF) am 28.10.2009 . Abgerufen am 23.02.2010 .

[ES1996-13] Edelsbrunner, Herbert ; Shah, Nimish (1996). „Inkrementelles topologisches Umklappen funktioniert für reguläre Triangulierungen“. Algorithmica . 15 (3): 223–241 . doi : 10.1007/BF01975867 . S2CID 12976796 .

[Parallel-14] Blelloch, Guy; Gu, Yan; Shun, Julian; und Sun, Yihan. Parallelismus in randomisierten inkrementellen Algorithmen. Archiviert am 25.04.2018 in der Wayback Machine . SPAA 2016. doi:10.1145/2935764.2935766.

[Peterson-15] Peterson, Samuel. „Berechnung eingeschränkter Delaunay-Triangulationen in der Ebene“ . www.geom.uiuc.edu . Archiviert vom Original am 22. September 2017. Abgerufen am 25. April 2018 .

[Dwyer1987-16] Dwyer, Rex A. (November 1987). „Ein schnellerer Divide-and-Conquer-Algorithmus zur Konstruktion von Delaunay-Triangulierungen“. Algorithmica . 2 ( 1–4 ): 137–151 . doi : 10.1007/BF01840356 . S2CID 10828441 .

[Leach1992-17] Leach, G. (Juni 1992). „Verbesserung von Delaunay-Triangulationsalgorithmen im ungünstigsten Fall“. 4. Kanadische Konferenz für Computergeometrie . CiteSeerX 10.1.1.56.2323 .

[CMS1998-18] Cignoni, P.; C. Montani; R. Scopigno (1998). „DeWall: Ein schneller Divide-and-Conquer-Delaunay-Triangulationsalgorithmus in E ^d “. Computer-Aided Design . 30 (5): 333–341 . doi : 10.1016/S0010-4485(97)00082-1 .

[19] Ein Vergleich sequentieller Delaunay-Triangulationsalgorithmen „Archivierte Kopie“ (PDF) . Archiviert vom Original (PDF) am 08.03.2012 . Abgerufen am 18.08.2010 .{{cite web}}: CS1 Wartung: Archivierte Kopie als Titel ( Link )

[20] „Triangulationsalgorithmen und Datenstrukturen“ . www.cs.cmu.edu . Archiviert vom Original am 10. Oktober 2017. Abgerufen am 25. April 2018 .

[21] „S-hull“ (PDF) . s-hull.org . Archiviert (PDF) vom Original am 27.10.2013 . Abgerufen am 25. April 2018 .

[AK2013-22] Franz Aurenhammer; Rolf Klein; Der-tsai Lee (26. Juni 2013). Voronoi-Diagramme und Delaunay-Triangulationen . World Scientific Publishing Company. S. 197–. ISBN 978-981-4447-65-2Die

[AKI2012-23] Sterling J. Anderson, Sisir B. Karumanchi, Karl Iagnemma (5. Juli 2012). „Constraint-based planning and control for safe, semi-autonomous operation of vehicles“ (PDF) . 2012 IEEE Intelligent Vehicles Symposium . IEEE. doi : 10.1109/IVS.2012.6232153 . Archiviert vom Original (PDF) am 28. Februar 2019. Abgerufen am 27. Februar 2019 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

sich dieser Algorithmus

[ 11 ]

[ 12 ] Obwohl sich die Technik auf höhere Dimensionen erweitern lässt (wie Edelsbrunner und Shah

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[ 23 ]