Pengambilan sampel dari sel Voronoi suatu titik

Perbaiki satu set poin P ⊂ R d . Sekarang titik permintaan q tiba, dan tujuannya adalah menghasilkan titik r sampel secara seragam dari sel Voronoi q di set P ∪ { q } .$n$$P \subset \mathbb{R}^d$$q$$r$$q$$P \cup \{q\}$

Untuk keperluan pertanyaan ini, Anda dapat mengasumsikan bahwa sel Voronoi selalu dibatasi (misalnya q selalu terletak di cembung lambung P ).$q$$q$$P$

Adakah yang diketahui tentang masalah ini?

Beberapa kendala:

• Saya mungkin ingin lebih dari satu sampel dari sel Voronoi . Ini harus IID.$q$
• Saya diizinkan untuk memproses poin sebelumnya, tetapi saya tidak dapat menghabiskan waktu secara eksponensial dalam .$d$
• Sampel harus dihasilkan dalam waktu sublinear dalam dan polinomial dalam d idealnya.$n$$d$

Perhatikan bahwa aturan di atas tidak menghitung sel Voronoi secara eksplisit. Perhatikan juga bahwa meskipun pendekatan penolakan sampel akan menghasilkan sampel yang seragam, tidak jelas bagaimana melakukannya secara efisien.

Terlalu pendek untuk berkomentar ... Berikut ini adalah bla bla intuitif, dan jangan ragu untuk membelinya.

$q$$2^d$. Ini mungkin argumen yang lebih formal. Pilih satu set poin pada unit hypersphere sehingga sudut antara dua titik setidaknya, saya tidak tahu, 80 derajat. Kita tahu, bahwa seseorang dapat memilih sejumlah titik eksponensial pada bola tanpa terlalu banyak usaha jika dimensinya cukup besar. Sekarang, secara intuitif, untuk setiap bagian dari setengah titik, sel Voronoi dari pusat bola seharusnya memiliki volume hampir dua kali lipat bila dibandingkan dengan volume sel dengan semua titik. Ini secara tidak langsung menyiratkan Anda harus memeriksa semua poin untuk mendapatkan estimasi volume yang baik. Yang tampaknya menyiratkan, sekali lagi secara intuitif, bahwa pengambilan sampel secara seragam tidak akan mungkin, karena masalahnya tampaknya setara secara polinomi ...