Wyliczenie wykresów pochodzących z teselacji Delaunaya w 3D

Czy istnieje algorytm, który wylicza wykresy odpowiadające pewnej teselacji punktów Delaunaya w 3D?

Jeśli tak, to czy istnieje wydajna parametryzacja geometrii, która odpowiada dowolnemu „grafowi Delaunaya”?

Staram się wyliczyć systematycznie wszystkie stabilne geometrie cząsteczek o określonym składzie bez żadnej wiedzy z zakresu wiązania itp.

EDYCJA: Niech będzie zbiorem wykresów z wierzchołkami. Niech będzie mapą punktów w do wykresu odpowiadającego teselacji Delaunaya wspomnianych punktów w 3D. $G_N$ $N$ $D: \mathbb{R}^{3N} \to G_N$ $N$ $\mathbb{R}^3$

Jak wyliczyć (wydajnie)? $D(\mathbb{R}^{3N})$

Ponadto, biorąc pod uwagę wykres , jak mogę sparametryzować (wydajnie)? $g\in G_n$ $D^{-1}(g)$

EDYCJA: Przykład w 2D: Dla 4 punktów są 2 wykresy Delaunaya.

\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}$

Lub pokazane w sposób wyraźnie płaski:

Wykresy delaunay 2D dla 4 punktów

Pierwszy z tych wykresów można sparametryzować dowolną pozycją punktów 1, 2 i 4, tj. , podczas gdy punkt 3 będzie dowolnym punktem gdzie jest większy niż promień okrąg opisujący punkty 1, 2 i 4 wyśrodkowany na a jest pozycją punktu . $\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 Oddech śmierci
źródło

Co rozumiesz przez „wydajną parametryzację geometrii”. Nie jestem też chemikiem, więc co oznacza „stabilna geometria cząsteczek o określonym składzie”? Przy odrobinie wyjaśnienia może to być łatwe do znalezienia.

Gareth A. Lloyd

Dla punktów w pozycji ogólnej w 3D istnieją niezależne stopnie swobody ( dla środka masy i kolejne 3 stopnie dla głównych osi obrotu). Każdy taki zestaw ma trochę mozaiki Delaunaya. Chciałbym odwrócić ten proces: biorąc pod uwagę teselację Delaunaya, chcę sparametryzować wszystkie zestawy punktów , które doprowadziłyby do teselacji Delaunaya. Stabilna geometria to zbiór punktów w przestrzeni z powiązanymi dodatnimi wagami, dla których funkcjonalność energetyczna jest lokalnie minimalna.

N

$N$

3 N - 6

$3N-6$

3 N - 3

$3N-3$

N

$N$

N

$N$

Deathbreath

Czy chcesz znaleźć wszystkie możliwe triangulacje Delaunaya? Czy możesz coś wyjaśnić? Ustawiasz za to nagrodę, ale mam wrażenie, że dla wielu wciąż pytanie nie jest jasne.

Szabolcs

@Szabolcs: Mam nadzieję, że edycja wyjaśni problem.

Deathbreath

@Deathbreath trochę ... mogę zrozumieć, to dobrze, że trzeba znaleźć wszystkie wykresy, które może odpowiadać triangulacji Delaunay z jakiegoś zbioru punktów w 3D? Czy możesz podać konkretny przykład? Na przykład, w 2D dla 4 punktów, czy potrzebujesz wykresów i (ignorując punkty współliniowe)? (Cyfry reprezentują wierzchołki, a pary cyfr kończą się w mojej notacji.)

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

W Hartvigsen, D. .: Rozpoznawanie diagramów Voronoi za pomocą programowania liniowego przedstawiono kilka algorytmów opartych na programowaniu liniowym do rozpoznawania teselacji Voronoi i stwierdza, że

[...] dla każdego diagramu Voronoi, zbiór punktów w zawarty w jakimś zestawie generacyjnym $R_i$ $R_i$ $P$

Wydaje się, że temat istnienia i wyjątkowości rozwiązania odwrotnego problemu Voronoi jest również rozwinięty w Winter, LG: Problem odwrotny do diagramu Voronoi .

astrojuanlu
źródło

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$

Po zrozumieniu twoich obaw i przeprowadzeniu badań znalazłem potencjalnie przydatne zasoby. Zauważ jednak, że nie potrafię odczytać pełnotekstowej wersji żadnego z nich.

astrojuanlu

To są interesujące referencje. Poproszę bibliotekę o dostarczenie mi kopii.

Deathbreath

Wygląda na to, że te referencje są trudniejsze do uzyskania niż oczekiwano.

Deathbreath

W każdym razie dziękuję za nagrodę, mam nadzieję, że przydadzą się, kiedy w końcu je dostaniesz.

astrojuanlu

Wyliczenie wykresów pochodzących z teselacji Delaunaya w 3D

Odpowiedzi: