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

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. $G_N$ $N$ $D: \mathbb{R}^{3N} \to G_N$ $N$ $\mathbb{R}^3$

Comment énumérer (efficacement)? $D(\mathbb{R}^{3N})$

De plus, étant donné un graphe , comment puis-je paramétrer (efficacement)? $g\in G_n$ $D^{-1}(g)$

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

\begin{matrix} 1 & - & 2 & - & 3 \\ ╲ & | & ╱ \\ 4 \end{matrix} and \begin{matrix} 1 & - & 2 \\ | & \times & | \\ 3 & - & 4 \end{matrix}

$\begin{matrix} 1 & - & 2 & - & 3 \\ &\diagdown &| & \diagup\\ &&4 \end{matrix}\mbox{ and } \begin{matrix} 1 & - & 2\\ |& \times & |\\ 3 & - & 4 \end{matrix}$

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 . $\mathbb{R}^{3\times 3}$ $x_3(r,\theta)=c(x_1,x_2,x_4) + r\left(\begin{array}{c} \cos(\theta) \\ \sin(\theta)\end{array}\right)$ $r$ $c(x_1,x_2,x_4)$ $x_i$ $i$

algorithms computational-chemistry delaunay-triangulation 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.

N

$N$

3 N - 6

$3N-6$

3 N - 3

$3N-3$

N

$N$

N

$N$

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.)

N

$N$

(12, 23, 31, 24, 43)

$(12, 23, 31, 24, 43)$

(12, 23, 31, 14, 24, 34)

$(12, 23, 31, 14, 24, 34)$

Szabolcs

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

$R_i$ $R_i$ $P$

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

3 N - 6

$3N-6$

3 N - 5

$3N-5$

D : R^{3 N} \to G_{N}

$D: \mathbb{R}^{3N} \to G_N$

G_{N}

$G_N$

N

$N$

N

$N$

D^{- 1} : G_{N} \to P (R^{3 N - 6})

$D^{-1}: G_N\to P(\mathbb{R}^{3N-6})$

D (R^{N})

$D(\mathbb{R}^N)$

D^{- 1} (g)

$D^{-1}(g)$

g \in G_{N}

$g\in G_N$

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

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

Réponses: