Apa struktur data / konsep ini di mana plot poin mendefinisikan partisi ke ruang

15

Saya menemukan algoritma untuk memecahkan masalah dunia nyata, dan saya ingat kelas yang saya ambil di mana saya membuat sesuatu yang sangat mirip untuk beberapa masalah pekerjaan rumah. ini terlihat seperti ini

Pada dasarnya ini adalah plot poin, dan garis-garisnya ditarik agar berjarak sama antara dua poin. Ini membentuk partisi sempurna di mana garis-garis di sekitar titik membentuk bentuk area yang paling dekat dengan titik itu. Apakah ini membunyikan bel untuk siapa pun? Saya mengalami kesulitan dalam deskripsi googling dan mendapatkan hasil. Dan saya tidak tahu bagaimana menggambarkannya. Semoga gambarnya membantu.

Brian
sumber
Dilihat 1667 kali sejak kemarin? Apakah SE diretas?
HEKTO
@HEKTO itu ditampilkan sebagai salah satu "Pertanyaan Jaringan Panas".
John L.

Jawaban:

31

Apa yang Anda gambarkan adalah diagram Voronoi .

Ini adalah kutipan dari Wikipedia.

Gambar diagram Voronoi dari Wikipedia

hal1,,halnhalkRkhalkkurang dari atau sama dengan jaraknya ke titik lain. Setiap sel tersebut diperoleh dari persimpangan setengah-ruang, dan karenanya merupakan poligon cembung. Segmen garis diagram Voronoi adalah semua titik dalam bidang yang berjarak sama dengan dua lokasi terdekat. Verteks Voronoi (simpul) adalah titik yang berjarak sama dengan tiga (atau lebih) situs.

John L.
sumber
4
+1. Saya menahan diri untuk tidak menyebutkannya dan pergi untuk implementasi karena saya ingat profesor saya menyebutkannya dengan catatan kaki bahwa Diagram Voronoi secara komputasi cukup kompleks untuk diimplementasikan dalam dimensi yang lebih tinggi. Jadi implementasi kNN yang sederhana menyelesaikan pekerjaan dengan lebih baik. Namun kondisi bahwa "garis ditarik agar sama antara dua titik" mungkin tidak terpenuhi.
Sagnik