Aufzählung von Graphen aus Delaunay-Tessellationen in 3D

12

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 NG N eine Karte von N Punkten in R 3 zu einem Graphen, der einer Delaunay-Tessellation dieser Punkte in 3D entspricht.GNND:R3NGNNR3

Wie zähle ich (effizient) auf?D(R3N)

Wie kann ich bei einem gegebenen Graphen D - 1 ( g ) (effizient) parametrieren ?gGnD1(g)

BEARBEITEN: Beispiel in 2D: Für 4 Punkte gibt es 2 Delaunay-Graphen.

123|4 and 12|×|34

Oder explizit eben dargestellt:

2D-Verzögerungsdiagramme für 4 Punkte

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 ,R3×3x3(r,θ)=c(x1,x2,x4)+r(cos(θ)sin(θ))r und x i ist die Position von Punkt i .c(x1,x2,x4)xii

Todeshauch
quelle
Was meinen Sie mit "effizienter Parametrisierung von Geometrien"? Ich bin auch kein Chemiker. Was bedeutet "stabile Geometrien von Molekülen einer bestimmten Zusammensetzung"? Mit etwas mehr Klarheit kann dies leicht beantwortet werden.
Gareth A. Lloyd
Für Punkte in der allgemeinen Position in 3D gibt es 3 N - 6 unabhängige Freiheitsgrade ( 3 N - 3 für den Schwerpunkt und weitere 3 Grad für die Hauptdrehachsen). Jedes dieser Sets hat eine gewisse Delaunay-Tesselation. Ich möchte diesen Prozess umkehren: Bei einer Delaunay-Tesselation möchte ich eine Parametrisierung aller Sätze von N Punkten, die zu dieser Delaunay-Tesselation führen würden. Eine stabile Geometrie ist eine Menge von N Punkten im Raum mit zugehörigen positiven Gewichten, für die die Energiefunktion lokal minimal ist. N3N63N3NN
Death Breath
Fragen Sie nach allen möglichen Delaunay-Triangulationen? Können Sie etwas klarstellen? Sie haben ein Kopfgeld dafür gezahlt, aber ich habe das Gefühl, dass die Frage für viele immer noch nicht klar ist.
Szabolcs
@ Szabolcs: Ich hoffe die Bearbeitung klärt das Problem.
Deathbreath
@Deathbreath ein wenig ... verstehe ich es richtig , dass Sie alle Diagramme finden müssen , die zu einer Delaunay - Triangulation entsprechen könnten einige Reihe von Punkten in 3D? Können Sie ein konkretes Beispiel nennen? Sind beispielsweise in 2D für 4 Punkte die benötigten Diagramme ( 12 , 23 , 31 , 24 , 43 ) und ( 12 , 23 , 31 , 14 , 24 , 34 ) (kollineare Punkte werden ignoriert)? (Die Ziffern repräsentieren Eckpunkte und die Kanten der Ziffernpaare in meiner Notation.)N(12,23,31,24,43)(12,23,31,14,24,34)
Szabolcs

Antworten:

4

In Hartvigsen, D .: Erkennen von Voronoi-Diagrammen mit linearer Programmierung werden verschiedene Algorithmen vorgestellt, die auf linearer Programmierung zum Erkennen von Voronoi-Tesellationen basieren

[...] Für jedes eines Voronoi-Diagramms ist die Menge der Punkte in R i, die in einer Erzeugungsmenge P enthalten ist, entweder ein Singleton oder das Innere eines Polyeders.RiRiP

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 .

Astrojuanlu
quelle
Es gibt nur relevante DoF ( 3 N - 5, wenn die Punkte auf einer Linie liegen), da entweder die Tesselation (Voronoi oder Delaunay) translatorisch und rotatorisch invariant ist. Ich meinte Delaunay-Tetraeder (oder allgemeiner Tesselation). Die Karte D : R 3 NG N , wobei G N die Menge von Graphen mit N Eckpunkten ist, die eine Menge von N Punkten in 3D auf den der Delaunay-Tesselation entsprechenden Graphen abbildet, hat eine theoretische Inverse D - 1 : G N3N63N5D:R3NGNGNNN . Ich nehme an, Ihre Antwort lautet: a) D ( R N ) ist nicht effizient berechenbar, b) und D - 1 ( g ) ( g G N ) auch nicht? D1:GNP(R3N6)D(RN)D1(g)gGN
Deathbreath
Nachdem ich Ihre Bedenken verstanden und einige Nachforschungen angestellt habe, habe ich einige potenziell nützliche Ressourcen gefunden. Beachten Sie jedoch, dass ich die Volltextversion von keinem von ihnen lesen kann.
Astrojuanlu
Das sind interessante Referenzen. Ich werde mir von meiner Bibliothek Kopien liefern lassen.
Deathbreath
Es scheint, dass diese Refs schwerer zu bekommen sind als erwartet.
Deathbreath
Trotzdem vielen Dank für das Kopfgeld, ich hoffe sie sind nützlich, wenn Sie sie endlich bekommen.
Astrojuanlu