Énumération des graphiques issus des pavages de Delaunay en 3D

12

Existe-t-il un algorithme qui énumère les graphiques qui correspondent à une tessellation Delaunay de points en 3D?

Dans l'affirmative, existe-t-il une paramétrisation efficace des géométries correspondant à tout "graphe de Delaunay"?

Je cherche à énumérer systématiquement toutes les géométries stables de molécules d'une composition spécifiée sans aucune connaissance a priori du collage etc.

EDIT: Soit l'ensemble des graphes avec sommets. Soit une carte de points dans vers un graphe correspondant à une pavage Delaunay desdits points en 3D. N D : R 3 NG N N R 3GNND:R3NGNNR3

Comment énumérer (efficacement)?D(R3N)

De plus, étant donné un graphe , comment puis-je paramétrer (efficacement)?D - 1 ( g )gGnD1(g)

EDIT: Exemple en 2D: pour 4 points il y a 2 graphes de Delaunay.

123|4 and 12|×|34

Ou représenté d'une manière explicitement plane:

Graphiques 2D Delaunay pour 4 points

Le premier de ces graphiques peut être paramétré par n'importe quelle position des points 1, 2 et 4, c'est-à-dire , tandis que le point 3 serait n'importe quel point où est plus grand que le rayon de le cercle circonscrivant les points 1, 2 et 4 centré en et est la position du point . x 3 (r,θ)=c( x 1 , x 2 , x 4 )+r ( cos ( θ ) sin ( θ ) ) rc( x 1 , x 2 , x 4 ) x i iR3×3x3(r,θ)=c(x1,x2,x4)+r(cos(θ)sin(θ))rc(x1,x2,x4)xii

Dernier soupir
la source
Qu'entendez-vous par "paramétrage efficace des géométries". Je ne suis pas non plus chimiste, alors que signifie "géométries stables de molécules d'une composition spécifiée"? Avec un peu plus de précision, cela peut être facilement répondu.
Gareth A. Lloyd
Pour points en position générale en 3D, il y a degrés de liberté indépendants ( pour le centre de masse et encore 3 degrés pour les principaux axes de rotation). Chacun de ces ensembles a une tesselation Delaunay. Je voudrais inverser ce processus: étant donné une tesselation de Delaunay, je veux une paramétrisation de tous les ensembles de points qui conduiraient à cette tesselation de Delaunay. Une géométrie stable est un ensemble de points dans l'espace avec des poids positifs associés pour lesquels l'énergie fonctionnelle est localement minimale. 3 N - 6 3 N - 3 N NN3N63N3NN
Deathbreath
Demandez-vous de trouver toutes les triangulations de Delaunay possibles? Pouvez-vous clarifier un peu? Vous définissez une prime à ce sujet, mais j'ai le sentiment que la question n'est toujours pas claire pour beaucoup.
Szabolcs
@Szabolcs: J'espère que l'édition clarifie le problème.
Deathbreath
@Deathbreath un peu ... Dois-je comprendre que vous devez trouver tous les graphiques qui pourraient correspondre à une triangulation de Delaunay d' un ensemble de points en 3D? Pouvez-vous donner un exemple précis? Par exemple, en 2D pour 4 points, avez-vous besoin des graphiques et (en ignorant les points colinéaires)? (Les chiffres représentent les sommets et les paires de chiffres bords dans ma notation.)( 12 , 23 , 31 , 24 , 43 ) ( 12 , 23 , 31 , 14 , 24 , 34 )N(12,23,31,24,43)(12,23,31,14,24,34)
Szabolcs

Réponses:

4

Dans Hartvigsen, D.: Reconnaître les diagrammes de Voronoi avec la programmation linéaire, plusieurs algorithmes basés sur la programmation linéaire pour reconnaître les tesellations de Voronoi sont présentés, et déclare que

RiRiP

Il semble que le sujet de l'existence et de l'unicité de la solution au problème inverse de Voronoi soit également développé dans Winter, LG: Le problème inverse au diagramme de Voronoi .

astrojuanlu
la source
3N63N5D:R3NGNGNNND1:GNP(R3N6)D(RN)D1(g)gGN
Après avoir compris vos préoccupations et fait quelques recherches, j'ai trouvé des ressources potentiellement utiles. Notez cependant que je ne peux lire la version intégrale d'aucun d'entre eux.
astrojuanlu
Ce sont des références intéressantes. Je vais demander à ma bibliothèque de me fournir des copies.
Deathbreath
Il semble que ces arbitres soient plus difficiles à obtenir que prévu.
Deathbreath
Merci quand même pour la prime, j'espère qu'ils vous seront utiles lorsque vous les obtiendrez enfin.
astrojuanlu