Kotak sejajar sumbu terkecil yang berisi titik

Input: Satu set poin dalam , dan integer . $n$ $\mathbb{R}^3$ $k \le n$

Output: Kotak pembatas sumbu-rata volume terkecil yang berisi setidaknya dari poin ini. $k$ $n$

Saya ingin tahu apakah ada algoritma yang dikenal untuk masalah ini. Yang terbaik yang bisa saya pikirkan adalah waktu , secara longgar sebagai berikut: kekuatan kasar atas semua batas atas dan bawah yang mungkin untuk dua dari tiga dimensi; untuk masing-masing kemungkinan , kita dapat menyelesaikan versi dimensi dari masalah dalam waktu menggunakan algoritma jendela geser. $O(n^5)$ $O(n^4)$ $1$ $O(n)$

cg.comp-geom GMB
sumber

Tidak bisakah kita menghitung tabel ukuran

untuk jumlah poin

dengan

? Menghitung jumlah poin dan volume dapat dilakukan dengan jumlah operasi const, dan kita dapat menggunakan pemrograman dinamis dengan tabel ukuran

dan harus bisa mendapatkan algoritma

n^{3}

$n^3$

p

$p$

p . x < x, p . y < y, p . z < z

$p.x< x, p.y<y, p.z <z$

k n^{3}

$k n^3$

O (k n^{3})

$O(kn^3)$

Kaveh

Baik. Dalam hal ini, bahwa

, Anda tidak dapat benar-benar berharap untuk melakukan yang lebih baik daripada

. Karena, ada

kotak berbeda, dan dengan rata-rata argumen (pada nilai acak k) ada

kotak yang berisi tepat titik k. Kecuali jika Anda entah bagaimana dapat menggunakan volume thingy untuk memperkecil ruang pencarian, tetapi entah bagaimana itu tampak optimis ...

k = Θ (n)

$k=\Theta(n)$

n^{5}

$n^5$

n^{6}

$n^6$

n^{5}

$n^5$

Sariel Har-Peled

BTW, dalam kasus Anda, Anda bisa mendapatkan kotak yang berisi

poin, dan itu lebih kecil dari kotak optimal yang mengandung poin

waktu. Untuk

ini pada dasarnya adalah waktu polylog., ..

(1 - ϵ) k

$(1-\epsilon)k$

k

$k$

O (((n / k) / ϵ^{2} \log n)^{O (1)})

$O( ((n/k)/\epsilon^2 \log n)^{O(1)})$

k = Θ (n)

$k = \Theta(n)$

Sariel Har-Peled

Jawaban:

Untuk poin ada kotak kosong, lihat pengantar makalah ini http://www.cs.uwm.edu/faculty/ad/maximal.pdf . Seseorang dapat menghitung kotak-kotak ini secara kasar kali ini (lihat intro untuk referensi). $n$ $O(n^3)$

Untuk masalah Anda, ambil sampel titik secara acak, di mana setiap titik diambil dengan tingkat kepekaan . Sampel acak semacam itu memiliki ukuran (dengan harapan) [dan demi kontradiksi anggaplah demikian]. Ada kotak kosong yang memiliki poin dari di sisinya, di atas. Untuk setiap kotak seperti itu, gunakan rentang ortogonal yang mencari struktur data untuk menghitung berapa banyak poin yang dikandungnya. Ulangi proses ini $1/k$ $n/k$ $O((n/k)^3)$ $R$ $O(k^6 \log n)$ waktu. Dengan probabilitas tinggi, salah satu kotak yang Anda coba adalah kotak yang diinginkan.

Secara keseluruhan, waktu menjalankan ini adalah . $O((n/k)^3 * k^6 * polylog n) = O(n^3 k^3 \log^{O(1)} n )$

Untuk melihat mengapa ini bekerja, pertimbangkan kotak yang optimal. Ini memiliki 6 poin P pada batasnya. Probabilitas bahwa sampel acak memilih enam poin ini, dan tidak ada satu pun poin di dalam kotak setidaknya . Jadi, jika Anda mengulangi proseskali, dengan probabilitas tinggi salah satu sampel acak akan menginduksi kotak yang diinginkan sebagai kotak kosong. $\frac{1}{k^6} ( 1-1/k)^{k-6} \approx 1/k^6 = p$ $O( (1/p) \log n)$

Karena ketat untuk jumlah kotak kosong (lihat intro kertas di atas untuk referensi yang relevan), tampaknya tidak mungkin bahwa algoritma yang lebih cepat secara signifikan dimungkinkan. $\Theta(n^3)$

[Dalam referensi yang saya berikan, mereka menyebutkan bahwa [17] menyediakan algoritma yang menyebutkan semua kotak kosong maksimal di antara titik dalam 3d dalam waktu , yang merupakan kotak hitam yang Anda butuhkan untuk yang di atas.] $O(n^3 \log^2 n)$

Sariel Har-Peled
sumber

Terima kasih - ini brilian! Detail yang benar-benar harus saya sebutkan (maaf!) Adalah bahwa

untuk tujuan saya, jadi

hanya sekitar sama baiknya dengan

. Namun, masih ada banyak ide keren di sini yang mungkin berguna untuk versi

besar ...

k = Θ (n)

$k = \Theta(n)$

O (n^{3} k^{3})

$O(n^3 k^3)$

O (n^{6})

$O(n^6)$

k

$k$

GMB