Das Konzept der Delaunay-Zerlegung geht auf das Jahr 1934 zurück. Diese Methode
ermöglicht es, einen n-dimensionalen konvexen Polyeder in Simplexe
zu zerlegen. Die charakteristische Eigenschaft einer Delaunay-Zerlegung
zweidimensionaler Gebiete ist, daß innerhalb des Umkreises jedes Dreiecks
keine Eckpunkte anderer Dreiecke liegen (Abbildung 5.3).
Eine Zerlegung dreidimensionaler Objekte fordert, daß innerhalb der Umkugel eines Tetraeders keine Eckpunkte anderer Tetraeder liegen (Abbildung 5.7). Eine Zerlegung nach dieser Methode, von einer gegebenen Punktwolke ausgehend, ergibt ein konvexes Gitter mit der bestmöglichsten Gitterqualität. Es werden die Elemente so gebildet, daß innerhalb der Elemente die minimalen Winkel maximiert werden. Eine weitere vorteilhafte Eigenschaft der Delaunay-Zerlegung liegt in der Möglichkeit, eine lokale Gitterverfeinerung durchzuführen. Soll der in Abbildung 5.3 angedeutete Punkt in Dreieck (4,7,5) eingefügt werden, so sind Dreiecke, innerhalb von deren Umkreisen der neue Punkt liegt, zu entfernen. Es sind also die Dreiecke (3,7,4) und (4,5,2) zu löschen, und dieses star shaped Polygon ist durch neue Verbindungen - von Punkt 8 zu 3,7,5 und 4 - zu vier neuen Dreiecken zu vergittern.
Die angegebene Verfeinerungsstrategie läßt sich auch als Zerlegungsalgorithmus im n-dimensionalen Raum verwenden [Wat81][Slo84]. Dazu wird ein Simplex gebildet, der die Punktwolke umschließt. Es wird willkürlich ein Punkt aus der Wolke ausgewählt und mit Hilfe der angegebenen Verfeinerungstragegie vergittert. Nach diesem Schema werden alle Punkte der Wolke aufgearbeitet. Es entsteht ein n-dimensionaler konvexer Polyeder, der noch nachbearbeitet werden muß. Die Punkte des umschließendenden Simplexes müssen entfernt werden, und jedes generierte Element, das nicht zur Struktur gehört, also außerhalb der ursprünglichen Objektberandung liegt, muß ebenfalls entfernt werden [Sch90].
