Bagaimana masalah trioulasi Voronoi Tesselation dan Delaunay saling rangkap?

Saya selalu diberi tahu bahwa diagram Voronoi adalah dual dari masalah triangulasi Delaunay. Dalam hal apa mereka bisa dua rangkap satu sama lain? Saya berpikir bahwa masalah ganda (yaitu dalam pemrograman linier) seharusnya menghasilkan jawaban yang sama. Yang jelas, kedua masalah tersebut tidak memiliki solusi yang sama. Bagaimana kita bisa menganggapnya dual?

Jawaban sederhananya adalah dobel karena untuk setiap triangulasi delaunay ada satu dan hanya satu voronoi yang sesuai dengan penilaian dan sebaliknya. Itu benar untuk sebagian besar kasus, tetapi ada kasus yang korespondensi tidak satu banding satu. Misalnya dalam kasus ketika voronoi tessellation adalah kotak persegi biasa.

Baik voronoi tessellation dan triangulasi delaunay adalah non-sepele untuk menghitung set poin yang diberikan. Tetapi sekali Anda telah menemukan satu yang lain mudah ditemukan.

$P$

$P$$R$$R_i$$P_i$$P$

Dengan adanya triangulasi delaunay, sambungkan saja pusat-pusat lingkaran segitiga yang berdekatan.

$P$$P$

Hanya untuk menggambarkan apa yang orang lain katakan: biru di bawah adalah diagram Voronoi, merah triangulasi Delaunay ganda. Mereka dobel satu sama lain sebagai grafik bidang geometris. Dari diagram Voronoi, sepele untuk menurunkan triangulasi Delaunay. Arah sebaliknya tidak begitu jelas, tetapi tetap benar bahwa dari triangulasi Delaunay dan beberapa perhitungan Anda dapat menghitung diagram Voronoi.
          
Saya menghitung diagram ini untuk 50 poin acak di Mathematica menggunakan paket ComputationalGeometry . Lihat tautan ini untuk kode saya.

${\bf P}$${\bf G}$$G_i$$P_i$$P_j \in {\bf P}, j \neq i$${\bf P}$

Dalam arti tertentu, ini mirip dengan dualitas yang ada antara kisi segitiga dan heksagonal dalam fisika statistik. Titik tengah sel dalam kisi segitiga sama sisi, ketika terhubung membentuk kisi heksagonal, dan sebaliknya .

Namun, harus ditunjukkan bahwa tidak semua transaksi Voronoi adalah dual triangulasi Delaunay; hubungan ini mungkin hanya berlaku untuk transaksi Voronoi tanpa bobot . Untuk metode tessellation tertimbang, di mana sesuatu selain jarak Euclidean digunakan untuk menentukan tepi, korresponensi terpecah.

Untuk menguraikan komentar Geoff: triangulasi Delaunay dan diagram Voronoi adalah "objek" daripada "masalah". Oleh karena itu, berbicara tentang "solusi" agak tidak menyenangkan.

Dualitasnya adalah antara tessalations dan triangulasi: Untuk berpindah dari triangulasi ke tesselation, Anda membentuk kumpulan simpul vertono dari Voronoi. Untuk berpindah dari saluran Voronoi ke triangulasi Delaunay, Anda menghubungkan "titik tengah" dari dua sel jika keduanya saling bersentuhan.

Grafik Voronoi dan Delaunay disebut ganda untuk properti grafiknya. Lihat Grafik Ganda di Wikipedia.