Enumerasi grafik berasal dari tessellations Delaunay dalam 3D

Apakah ada algoritma yang menyebutkan grafik yang sesuai dengan beberapa titik tunda Delaunay dalam 3D?

Jika ya, adakah parameterisasi geometri efisien yang sesuai dengan "grafik Delaunay"?

Saya mencari untuk menghitung secara sistematis semua geometri molekul yang stabil dari komposisi tertentu tanpa pengetahuan apriori tentang ikatan dll.

EDIT: Biarkan menjadi himpunan grafik dengan simpulBiarkan menjadi peta titik di ke grafik yang terkait dengan penghentian Delaunay dari titik-titik tersebut dalam 3D. $G_N$ $N$ $D: \mathbb{R}^{3N} \to G_N$ $N$ $\mathbb{R}^3$

Bagaimana cara saya menghitung (efisien)? $D(\mathbb{R}^{3N})$

Selanjutnya, diberikan grafik , bagaimana saya bisa membuat parameter (efisien)? $g\in G_n$ $D^{-1}(g)$

EDIT: Contoh dalam 2D: Untuk 4 poin ada 2 grafik 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}$

Atau ditampilkan dengan cara planar eksplisit:

Grafik delaunay 2D untuk 4 poin

Yang pertama dari grafik ini dapat diparameterisasi dengan posisi mana pun dari titik 1, 2 dan 4, yaitu, , sedangkan titik 3 adalah titik mana lebih besar dari jari-jari lingkaran membatasi titik 1, 2, dan 4 berpusat pada dan adalah posisi titik . $\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 Deathbreath
sumber

Apa yang Anda maksud dengan "parameterisasi geometri yang efisien". Saya juga bukan ahli kimia, jadi apa artinya "geometri molekul stabil dari komposisi tertentu"? Dengan sedikit klarifikasi, ini mungkin mudah dijawab.

Gareth A. Lloyd

Untuk titik dalam posisi umum dalam 3D, ada derajat kebebasan independen ( untuk pusat massa dan 3 derajat lainnya untuk sumbu rotasi utama). Setiap set memiliki beberapa acara Delaunay. Saya ingin membalikkan proses ini: mengingat tesselation Delaunay, saya ingin parameterisasi semua set poin yang akan mengarah pada tesselation Delaunay ini. Geometri stabil adalah sekumpulan titik di ruang angkasa dengan bobot positif terkait yang fungsi energinya minimal secara lokal.

N

$N$

3 N - 6

$3N-6$

3 N - 3

$3N-3$

N

$N$

N

$N$

Deathbreath

Apakah Anda meminta untuk menemukan semua kemungkinan triangulasi Delaunay? Bisakah Anda menjelaskan sedikit? Anda menetapkan karunia untuk ini, tetapi saya merasa pertanyaannya masih belum jelas bagi banyak orang.

Szabolcs

@Szabolcs: Saya harap hasil edit menjelaskan masalahnya.

Deathbreath

@Deathbreath sedikit ... apakah saya mengerti benar bahwa Anda perlu menemukan semua grafik yang dapat sesuai dengan triangulasi Delaunay dari beberapa set poin dalam 3D? Bisakah Anda memberikan contoh spesifik? Misalnya, dalam 2D untuk 4 poin, apakah grafik yang Anda butuhkan dan (mengabaikan titik collinear)? (Digit mewakili simpul dan digit pasang di notasi saya.)

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

Dalam Hartvigsen, D .: Mengenali Diagram Voronoi dengan Linear Programming beberapa algoritma berdasarkan pemrograman linier untuk mengenali tes Voronoi disajikan, dan menyatakan bahwa

[...] untuk setiap dari diagram Voronoi, himpunan titik dalam terkandung dalam beberapa himpunan adalah salah satu dari singleton atau interior polyhedron. $R_i$ $R_i$ $P$

Tampaknya topik keberadaan dan keunikan solusi untuk masalah Voronoi terbalik juga dikembangkan di Winter, LG: Masalah terbalik ke diagram Voronoi .

astrojuanlu
sumber

Hanya ada DoF yang relevan ( jika poinnya berada pada satu garis) sebagai tesselation (Voronoi atau Delaunay) yang secara invarian dan bergiliran bergiliran. Maksud saya Delaunay tetrahedration (atau lebih tepatnya tesselation). Peta , di mana adalah himpunan grafik dengan simpul , yang memetakan serangkaian titik dalam 3D ke grafik yang sesuai dengan tesselation Delaunay memiliki pembalikan teoritis . Saya menganggap jawaban Anda adalah: a) tidak dapat dihitung secara efisien, b) dan tidak juga ( )?

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$

Deathbreath

Setelah memahami kekhawatiran Anda dan melakukan penelitian, saya telah menemukan beberapa sumber daya yang berpotensi bermanfaat. Namun perlu dicatat bahwa saya tidak dapat membaca versi teks lengkap dari mereka.

astrojuanlu

Itu referensi yang menarik. Perpustakaan saya akan memberikan salinan kepada saya.

Deathbreath

Tampaknya para referensi ini lebih sulit untuk mendapatkan daripada yang diantisipasi.

Deathbreath

Terima kasih untuk hadiahnya, semoga bermanfaat saat kamu akhirnya mendapatkannya.

astrojuanlu

Enumerasi grafik berasal dari tessellations Delaunay dalam 3D

Jawaban: