Bagaimana tidak menghitung lingkaran terkecil yang melampirkan satu set lingkaran terbatas

Misalkan kita memiliki himpunan berhingga disk di , dan kami ingin menghitung disk terkecil yang . Sebuah cara standar untuk melakukan ini adalah dengan menggunakan algoritma Matoušek, Sharir dan Welzl [1] untuk menemukan dasar dari , dan biarkan , yang terkecil disk yang berisi . Disk dapat dihitung secara aljabar menggunakan fakta bahwa, karena adalah basis, setiap disk dalam bersinggungan dengan .R 2 D ⋃ L ⊆ D B L D = ⟨ B ⟩ ⋃ B ⟨ B ⟩ B B ⟨ B $L$$\mathbb{R}^2$$D$$\bigcup L\subseteq D$$B$$L$$D=\langle B\rangle$$\bigcup B$$\langle B\rangle$$B$$B$$\langle B\rangle$

( adalah dasar dari jika B adalah minimal sehingga ⟨ B ⟩ = ⟨ L ⟩ Sebuah dasar memiliki paling banyak tiga elemen;. Secara umum untuk bola di dasar memiliki paling Elemen .)$B\subseteq L$$L$$B$$\langle B\rangle=\langle L\rangle$ d+$\mathbb{R}^d$$d+1$

Ini adalah algoritma rekursif acak sebagai berikut. (Tapi lihat di bawah untuk versi yang berulang, yang mungkin lebih mudah dimengerti.)

Prosedur : Input : Kumpulan disk hingga , , di mana adalah basis (dari ).$MSW(L, B)$
B B $L$$B$$B$$B$

1. Jika , kembali .$L=\varnothing$$B$
2. Kalau tidak, pilih$X\in L$ secara acak.
3. Biarkan .$B'\leftarrow MSW(L-\{X\}, B)$
4. Jika maka kembalikan .$X\subseteq\langle B'\rangle$$B'$
5. Kalau tidak, kembalikan , di mana adalah basis dari .B ″ B ′ ∪ { X $MSW(L, B'')$$B''$$B'\cup\{X\}$

Digunakan sebagai $MSW(L, \varnothing)$ untuk menghitung dasar $L$ .

Baru-baru ini saya punya alasan untuk mengimplementasikan algoritma ini. Setelah memverifikasi bahwa hasilnya benar dalam jutaan kasus uji yang dibuat secara acak, saya perhatikan bahwa saya telah membuat kesalahan dalam implementasi. Pada langkah terakhir saya mengembalikan $MSW(L-\{X\}, B'')$ daripada $MSW(L, B'')$ .

Meskipun ada kesalahan ini, algoritma ini memberikan jawaban yang benar.

Ditambahkan: beberapa kesalahpahaman

Beberapa orang telah mengajukan argumen yang salah tentang efek bahwa algoritma yang dimodifikasi sepele benar, sehingga mungkin berguna untuk mencegah beberapa kesalahpahaman di sini. Satu kepercayaan keliru yang populer tampaknya adalah bahwa . Berikut adalah contoh tandingan terhadap klaim itu. Disk yang diberikan seperti di bawah ini (batas \ langle a, b, e \ rangle juga ditampilkan dalam warna merah):a , b , c , d , e ⟨ a , b , e $B\subseteq\langle MSW(L, B)\rangle$$a,b,c,d,e$$\langle a,b,e\rangle$

kita dapat memiliki $MSW(\{c, d\}, \{a,b,e\})=\{c,d\}$ ; dan perhatikan bahwa $e\notin\langle c,d\rangle$ :

Inilah yang bisa terjadi. Pengamatan pertama adalah bahwa :$MSW(\{c\},\{a,b,e\})=\{b,c\}$

• Kami ingin menghitung$MSW(\{c\},\{a,b,e\})$
• Pilih$X = c$
• Biarkan$B' = MSW(\varnothing, \{a,b,e\}) = \{a,b,e\}$
• Amati$X\notin\langle B'\rangle$
• Jadi, biarkan menjadi basis dariB ′ ∪ { X } = { a , b , c , e $B''$$B'\cup\{X\} = \{a,b,c,e\}$
• Perhatikan bahwa$B''=\{b,c\}$
• Kembalikan , yaitu{ b , c $MSW(\{c\}, \{b,c\})$$\{b,c\}$

Sekarang pertimbangkan .$MSW(\{c, d\}, \{a,b,e\})$

• Kami ingin menghitung$MSW(\{c, d\}, \{a,b,e\})$
• Pilih$X=d$
• Biarkan$B' = MSW(\{c\}, \{a,b,e\}) = \{b,c\}$
• Amati$X\notin\langle B'\rangle$
• Jadi mari menjadi dasar dariB ′ ∪ { X } = { b , c , $B''$$B'\cup\{X\} = \{b,c,d\}$
• Amati bahwa$B''=\{c,d\}$
• Kembalikan , yaitu{ c , d $MSW(\{c,d\}, \{c,d\})$$\{c,d\}$

(Demi kepastian, mari kita katakan bahwa disk semuanya memiliki radius 2, dan berpusat di , , , , dan masing-masing.)( 30 , 5 ) ( 30 , 35 ) ( 10 , 5 ) ( 60 , 26 ) ( 5 , 26 $a,b,c,d,e$$(30,5)$$(30,35)$$(10, 5)$$(60, 26)$$(5, 26)$

Ditambahkan: presentasi berulang

Mungkin lebih mudah untuk memikirkan presentasi algoritma yang berulang. Saya tentu merasa lebih mudah untuk memvisualisasikan perilakunya.

Input : Daftar disk Output : Dasar$L$
$L$

1. Biarkan .$B\leftarrow\varnothing$
2. Acak$L$ secara acak.
3. Untuk setiap di$X$$L$ :
4.   Jika :$X\notin\langle B\rangle$
5.     Biarkan menjadi basis .$B$$B\cup\{X\}$
6.     Kembali ke langkah 2.
7. Kembali .$B$

Alasan algoritme berakhir, secara kebetulan, adalah bahwa langkah 5 selalu meningkatkan jari-jari - dan hanya ada banyak kemungkinan nilai .$\langle B\rangle$$B$

Versi yang dimodifikasi tidak memiliki presentasi berulang yang sederhana, sejauh yang saya bisa lihat. (Saya mencoba memberikan satu di edit sebelumnya untuk posting ini, tetapi itu salah - dan memberikan hasil yang salah.)

Referensi

[1] Jiří Matoušek, Micha Sharir, dan Emo Welzl. Batas subeksponensial untuk pemrograman linier. Algorithmica, 16 (4-5): 498–516, 1996.

Langkah ini menghapus dari L sebelum melanjutkan rekursi sebenarnya meningkatkan algoritma, karena menghilangkan X yang sudah ditambahkan$X$$L$$X$ dari kumpulan kandidat dasar. Itu akan selalu, terbukti bekerja, karena itu setara dengan algoritma yang ada, dan itu juga akan bekerja untuk dimensi yang lebih tinggi.

Lacak melalui algoritma. Saat Anda menggunakan , ada X ∈ L dan X ∈ B ′ ′ . Misalkan kita memilihnya lagi pada langkah 2. Terlepas dari hasil langkah 3, B ′ akan selalu memiliki X , karena fungsi rekursif memiliki B ⊆ M S W ( L , B ) yang invarian$MSW(L,B^{\prime\prime})$$X \in L$$X \in B^{\prime\prime}$$B^\prime$$X$$B \subseteq MSW(L,B)$ .

Dengan kata lain, peningkatan Anda pada pintasan algoritma ke langkah 3 di bagian di mana dipilih.$X$