Kompleksitas untuk menemukan bola yang memaksimalkan jumlah poin di dalamnya

Diberikan seperangkat poin dan radius . Yaitu kompleksitas menemukan titik dengan jumlah titik lebih tinggi pada jarak lebih kecil dari . Misalnya yang memaksimalkan ? $x_1, \ldots, x_n \in \mathbb{R}^2$ $r$ $r$ $\sum_{i=1}^n \mathbb{1}_{\|x - x_i\| \leq r}$

Algoritma brute force akan memeriksa setiap titik dan menghitung jumlah titik yang jaraknya lebih kecil dari $r$ . Itu akan memberikan kompleksitas $\mathcal{O}(n^2)$ .

Apakah ada pendekatan yang lebih baik?

algorithms complexity-theory computational-geometry Manuel
sumber

Sudahkah Anda melihat pohon-pohon pemisah ruang quad dan biner? Saya akan mengantisipasi bahwa mereka mungkin memberikan algoritma yang lebih efisien dalam prakteknya, meskipun saya tidak tahu apa waktu berjalan asimptotik terburuk.

(Pusat dari balldari judul harus dari himpunan?) Satu ide mungkin untuk memperkirakan apakah jari-jari kecil dibandingkan dengan jarak rata-rata ke tetangga terdekat atau pada urutan diameter (dan mempertimbangkan pendekatan untuk ekstrem ini (Pesawat menyapu untuk kecil ) dan ruang yang luas di antara).

r

$r$

greybeard

Pusat bola harus tetapi jika ada algoritma yang lebih baik tanpa syarat saya juga tertarik.

x_{i}

$x_i$

Manuel

Sepertinya algoritma yang lebih cepat daripada untuk Ball Count Counting Problem tidak diketahui. Namun, jika Anda bisa menerima jawaban yang tidak tepat maka Anda dapat memperkirakan disk dengan seperangkat kotak dengan orientasi yang berbeda. Untuk setiap orientasi, Anda harus membuat Range Tree ( en.wikipedia.org/wiki/Range_tree ), yang memungkinkan Anda menghitung semua titik di dalam kotak dalam waktu (k - sejumlah poin yang dihasilkan).

O (n)

$O(n)$

O (l o g^{2} (n) + k)

$O(log^2(n) + k)$

HEKTO

@ HEKTO Apakah Anda menyarankan membangun struktur biaya untuk meminta jika suatu titik terletak pada persegi panjang dengan biaya ? Lalu pergi ke semua poin untuk menghitung berapa banyak poin lain terletak di bola yang diperkirakan? Ini bisa berhasil, tetapi kemudian, apa yang akan menjadi memori yang diperlukan untuk struktur data seperti itu? apakah lebih rendah dari ?

O (n \log (n))

$\mathcal{O}(n\log(n))$

O (l o g^{2} (n) + k)

$\mathcal O (log^2(n) + k)$

O (n^{2}))

$\mathcal O (n^2))$

Manuel

Jawaban:

Sepertinya algoritma sublinear untuk Ball Range Counting Problem belum diketahui untuk saat ini.

Namun, jika Anda bisa menerima jawaban yang tidak tepat maka Anda dapat memperkirakan disk dengan seperangkat kotak dengan orientasi yang berbeda. Untuk setiap orientasi Anda harus membangun Range Tree , yang memungkinkan Anda untuk menghitung semua titik di dalam kotak dalam waktu (k - sejumlah poin yang dihasilkan). $O(log^2(n)+k)$

Setiap rentang pohon akan membutuhkan memori , semakin baik perkiraan Anda ingin semakin banyak orientasi yang harus Anda gunakan. Misalnya, dua orientasi akan memberi Anda segi delapan , yang mendekati disk dengan kesalahan area kurang dari 6%. $O(n \cdot log(n))$

HEKTO
sumber

Jawabannya tidak begitu sederhana, ada studi lanjutan dari pertanyaan ini dalam teori kompleksitas; tampaknya dipelajari misalnya sebagai masalah berikut, yang difokuskan pada pertanyaan "penghitungan rentang bola" yang cepat. Ya, batas teoretis yang ditingkatkan dimungkinkan, tetapi ini tampaknya merupakan algoritma abstrak yang belum diterapkan oleh siapa pun. Jika Anda menginginkan implementasi aktual, itu adalah pertanyaan yang berbeda.

"Pengorbanan Ruang-Waktu untuk Perkiraan Penghitungan Kisaran Bulat" / Arya, Malamatos, Mount

vzn
sumber