Gibt es einen Algorithmus, der die Graphen auflistet, die einer Delaunay-Tessellation von Punkten in 3D entsprechen?
Wenn ja, gibt es eine effiziente Parametrisierung von Geometrien, die einem "Delaunay-Graphen" entsprechen?
Ich versuche, systematisch alle stabilen Geometrien von Molekülen einer bestimmten Zusammensetzung ohne vorherige Kenntnis der Bindung usw. aufzulisten.
BEARBEITEN: Sei die Menge der Graphen mit N Eckpunkten. Sei D : R 3 N → G N eine Karte von N Punkten in R 3 zu einem Graphen, der einer Delaunay-Tessellation dieser Punkte in 3D entspricht.
Wie zähle ich (effizient) auf?
Wie kann ich bei einem gegebenen Graphen D - 1 ( g ) (effizient) parametrieren ?
BEARBEITEN: Beispiel in 2D: Für 4 Punkte gibt es 2 Delaunay-Graphen.
Oder explizit eben dargestellt:
Der erste dieser Graphen kann durch eine beliebige Position der Punkte 1, 2 und 4 parametrisiert werden, dh , während Punkt 3 ein beliebiger Punkt x 3 ( r , θ ) = c ( x 1 , x 2 , x wäre 4 ) + r ( cos ( θ ) sin ( θ ) ) wobei r größer ist als der Radius des Kreises, der die Punkte 1, 2 und 4 umgibt, zentriert bei c ( x 1 , und x i ist die Position von Punkt i .
Antworten:
In Hartvigsen, D .: Erkennen von Voronoi-Diagrammen mit linearer Programmierung werden verschiedene Algorithmen vorgestellt, die auf linearer Programmierung zum Erkennen von Voronoi-Tesellationen basieren
Es scheint, dass das Thema der Existenz und Eindeutigkeit der Lösung des inversen Voronoi-Problems auch im Winter entwickelt wird. LG: Das inverse Problem zum Voronoi-Diagramm .
quelle