Diagram Voronoi dalam grafik

Biarkan menjadi grafik dengan sisi positif (berbobot). Saya ingin mendefinisikan diagram Voronoi untuk satu set node / situs , untuk mengasosiasikan dengan simpul subgraph dari yang disebabkan oleh semua node ketat lebih dekat dengan daripada node lain dalam , mengukur panjang lintasan dengan jumlah bobot pada busur. adalah 's wilayah Voronoi . Misalnya, simpul hijau di bawah ini ada di , dan simpul kuning ada di . $G$ $S$ $v \in S$ $R(v)$ $G$ $v$ $S$ $R(v)$ $v$ $R(v_1)$ $R(v_2)$
masukkan deskripsi gambar di sini
Saya ingin memahami struktur diagram Voronoi. Sebagai permulaan, seperti apa diagram dari dua situs dan , yaitu, seperti apa garis- garis 2-situs itu (biru pada contoh di atas)? Saya pikir dari garis- sebagai pelengkap dari di . Inilah dua pertanyaan spesifik: $v_1$ $v_2$ $B(v_1,v_2)$ $R(v_1) \cup R(v_2)$ $G$

Q1. Apakah bistor dari dua situs terhubung dalam arti tertentu?

Q2. Apakah cembung dalam arti bahwa ia mengandung jalur terpendek antara dua node dalam ? $R(v)$ $R(v)$

Tentunya ini sudah dipelajari sebelumnya. Adakah yang bisa memberikan referensi / petunjuk? Terima kasih!

Tambahan untuk komentar Suresh:
masukkan deskripsi gambar di sini

reference-request graph-theory cg.comp-geom Joseph O'Rourke
sumber

Agar Q1 masuk akal, Anda perlu akal sehat, bukan? Kalau tidak, "sebenarnya" garis tengah berada di tengah-tengah tepi, dan memperkenalkan simpul sebelum dan sesudah titik ini, menjamin bahwa garis luar itu terputus. Mungkin jika Anda menganggap grafiknya chordal, Anda dapat membuktikan sesuatu. Adapun Q2: ini salah bahkan untuk geodesik dalam poligon berlubang (atau medan). Dugaan saya adalah Anda perlu mengasumsikan sesuatu yang cukup kuat pada grafik untuk mendapatkan jawaban yang tidak sepele untuk kedua pertanyaan.

Sariel Har-Peled

Terima kasih, Sariel, atas pengamatan itu. Ya, sepertinya saya berharap terlalu banyak, dan mungkin hanya di kelas grafik khusus akan ada sifat struktural yang bagus.

Joseph O'Rourke

ah jadi di ruang biasa sel voronoi tidak bisa lebih besar dari belahan bumi, jadi Anda tidak punya masalah ini. Tetapi komentar saya secara umum sama dengan komentar Sariel bahwa Anda meminta sel-sel voronoi yang cembung dalam potensi rifen generik yang berlipat ganda dan itu seharusnya tidak benar.

Suresh Venkat

Untuk Q1, contoh tandingan yang lebih sederhana adalah garis bagi

mana

adalah sisi kiri

. Bisector benar-benar terputus.

S

$S$

S

$S$

K_{2, n}

$K_{2, n}$

Josephine Moeller

Jadi sekarang saya berpikir mungkin ada pertanyaan menarik di sini. Bagaimana jika metrik yang mendasarinya bermacam-macam (seperti yang disarankan oleh Suresh). Sekarang, kita menghubungkan dua titik jika dan hanya jika ada titik ketiga q, dua titik lainnya adalah dua tetangga terdekat (pikirkan ini sebagai semacam kompleks saksi). Dugaan alami adalah bahwa jika manifold berlipat ganda, maka orang dapat selalu menambahkan O (1) poin sedemikian rupa sehingga garis bagi terhubung. Hmmm ...

Sariel Har-Peled

Mehlhorn, K .: Algoritma perkiraan lebih cepat untuk masalah Steiner dalam grafik. Pemrosesan Informasi Surat 27, 125-128 (1988)

Erwig, M .: Grafik diagram Voronoi dengan aplikasi. Networks 36 (3), 156–163 (2000)

kedua referensi disalin dari

Matthew T. Dickerson, Michael T. Goodrich, Thomas D. Dickerson, Ying Daisy Zhuo: Round-Trip Diagram Voronoi dan Menggandakan Kepadatan di Jaringan Geografis. Transaksi pada Ilmu Komputasi 14: 211-238 (2011)

David Eppstein
sumber

Ini akan membutuhkan beberapa penggalian, tetapi secara dangkal, tampaknya tidak banyak sifat struktural diagram telah diidentifikasi dalam makalah ini (mungkin karena ada beberapa sifat catatan!).

Joseph O'Rourke

memang tidak banyak yang diketahui; kami memiliki satu atau dua lemma di sommer.jp/voronoi.htm

Christian Sommer

Diagram Voronoi dalam grafik

Jawaban: