Geometrie und Topologie
Fakultät für Mathematik
Technische Universität München

Das Inkreis-Prädikat

Durch Auswertung eines geeigneten Determinantenvorzeichens lässt sich beispielsweise auch entscheiden, ob sich ein Punkt innerhalb eines durch drei andere Punkte aufgespannten Kreises befindet.

Das Inkreis-Prädikat (und somit Determinanten) spielt auch eine entscheidende Rolle bei der Bestimmung einer so genannten Delauney-Triangulierung. Dies ist eine Triangulierung, bei der im Umkreis keines der beteiligten Dreiecke ein weiterer Punkt liegt.

Delauney-Triangulierungen spielen (neben der Tatsache, dass sie für viele weitere Anwendungen in der Optimierung und Computational Geometry von entscheidender Bedeutung sind,) eine wesentliche Rolle bei der Berechnung so genannter Voronoi-Diagramme.

Für eine gegebene Punktmenge ist die Voronoi-Region eines Punktes der Teil der Ebene, der näher an diesem Punkt als an irgendeinem anderen Punkt liegt. Im untenstehenden Applet ist die Voronoi-Zerlegung gelb eingezeichnet. Die Kanten des Voronoi-Diagramms sind genau die Mittelsenkrechten auf den Kanten der Delauney-Triangulierung.