Jak nie obliczyć najmniejszego okręgu zawierającego skończony zestaw kół

Załóżmy, że mamy skończony zbiór $L$ dysków w $\mathbb{R}^2$ , i chcemy obliczyć najmniejszą dysku $D$ , dla którego $\bigcup L\subseteq D$ . Standardowy sposób ten jest użycie algorytmu Matousek, Sharir i Welzl [1], aby znaleźć podstawę $B$ z $L$ i pozwolić $D=\langle B\rangle$ najmniejsza dysku zawierającej $\bigcup B$ . Dysk $\langle B\rangle$ może być obliczany algebraicznie wykorzystując fakt, że od $B$ to podstawa, każdy dysk w $B$ jest styczny do $\langle B\rangle$.

( $B\subseteq L$ jest podstawa z $L$ , jeśli $B$ jest minimalny, tak że $\langle B\rangle=\langle L\rangle$ podstawę, ma najwyżej trzy elementy, na ogół w kulki w $\mathbb{R}^d$ podstawa ma co najwyżej $d+1$ . Elementy)

Jest to randomizowany algorytm rekurencyjny w następujący sposób. (Ale zobacz poniżej iteracyjną wersję, która może być łatwiejsza do zrozumienia.)

Procedura : $MSW(L, B)$
wejściowe : Skończone zestawy dysków $L$ , $B$ , gdzie $B$ jest podstawą ( $B$ ).

1. Jeśli $L=\varnothing$ , zwróć $B$ .
2. W przeciwnym razie wybierz $X\in L$ losowo.
3. Niech .$B'\leftarrow MSW(L-\{X\}, B)$
4. Jeżeli następnie powrócić B ' .$X\subseteq\langle B'\rangle$$B'$
5. W przeciwnym przypadku powrót , w którym B " stanowi podstawę B ' ∪ { X } .$MSW(L, B'')$$B''$$B'\cup\{X\}$

Używane jako do obliczenia podstawy L .$MSW(L, \varnothing)$$L$

Ostatnio miałem powód do implementacji tego algorytmu. Po sprawdzeniu, że wyniki były prawidłowe w milionach losowo wygenerowanych przypadków testowych, zauważyłem, że popełniłem błąd przy implementacji. W ostatnim kroku zwracałem zamiast M S W ( L , B ″ ) .$MSW(L-\{X\}, B'')$$MSW(L, B'')$

Pomimo tego błędu algorytm dawał prawidłowe odpowiedzi.

Dodano: niektóre nieporozumienia

Kilka osób zaproponowało niepoprawne argumenty, że zmodyfikowany algorytm jest trywialnie poprawny, więc może być przydatne zapobieganie niektórym nieporozumieniom. Jednym z popularnych fałszywe przekonanie, wydaje się, że . Oto kontrprzykład na to twierdzenie. Biorąc pod uwagę, tarcz z , b , c , d , e , jak poniżej (granica ⟨ , b , e ⟩ również pokazano na czerwono):$B\subseteq\langle MSW(L, B)\rangle$$a,b,c,d,e$$\langle a,b,e\rangle$

możemy mieć ; i pamiętać, że e ∉ ⟨ c , d ⟩ :$MSW(\{c, d\}, \{a,b,e\})=\{c,d\}$$e\notin\langle c,d\rangle$

Oto jak to się może stać. Pierwsza obserwacja jest taka, że :$MSW(\{c\},\{a,b,e\})=\{b,c\}$

• Chcemy obliczyć $MSW(\{c\},\{a,b,e\})$
• Wybierz $X = c$
• Niech $B' = MSW(\varnothing, \{a,b,e\}) = \{a,b,e\}$
• Zauważmy, że $X\notin\langle B'\rangle$
• Niech więc będzie podstawą B ′ ∪ { X } = { a , b , c , e $B''$$B'\cup\{X\} = \{a,b,c,e\}$
• Zauważ, że $B''=\{b,c\}$
• Zwróć , czyli { b , c $MSW(\{c\}, \{b,c\})$$\{b,c\}$

Rozważmy teraz .$MSW(\{c, d\}, \{a,b,e\})$

• Chcemy obliczyć $MSW(\{c, d\}, \{a,b,e\})$
• Wybierz $X=d$
• Niech $B' = MSW(\{c\}, \{a,b,e\}) = \{b,c\}$
• Zauważmy, że $X\notin\langle B'\rangle$
• Niech więc będzie podstawą B ′ ∪ { X } = { b , c , d $B''$$B'\cup\{X\} = \{b,c,d\}$
• Zauważ, że $B''=\{c,d\}$
• Zwróć , czyli { c , d $MSW(\{c,d\}, \{c,d\})$$\{c,d\}$

(W celu określenia, powiedzmy, że wszystkie dyski mają promień 2 i są wyśrodkowane na ( 30 , 5 ) , ( 30 , 35 ) , ( 10 , 5 ) , ( Odpowiednio 60 , 26 ) i ( 5 , 26 ) .)$a,b,c,d,e$$(30,5)$$(30,35)$$(10, 5)$$(60, 26)$$(5, 26)$

Dodano: prezentacja iteracyjna

Łatwiej pomyśleć o iteracyjnej prezentacji algorytmu. Z pewnością łatwiej mi sobie wyobrazić jego zachowanie.

Dane wejściowe : lista dysków Dane wyjściowe : podstawa $L$
$L$

1. Niech $B\leftarrow\varnothing$ .
2. Losuj $L$ losowy.
3. Dla każdego w $X$$L$ :
4.   Jeśli $X\notin\langle B\rangle$ :
5.     Niech będzie podstawą B ∪ { X $B$$B\cup\{X\}$ .
6.     Wróć do kroku 2.
7. Powrót .$B$

Powodem, dla którego kończy algorytm, nawiasem mówiąc, jest to, że krok 5 zawsze zwiększa promień - i istnieje tylko skończenie wiele możliwych wartości $\langle B\rangle$$B$ .

O ile mi wiadomo, zmodyfikowana wersja nie ma tak prostej iteracyjnej prezentacji. (Próbowałem podać jedną w poprzedniej edycji tego postu, ale było to złe - i dałem nieprawidłowe wyniki).

Odniesienie

[1] Jiří Matoušek, Micha Sharir i Emo Welzl. Podwykładnicza granica programowania liniowego. Al Algorytmica, 16 (4-5): 498–516, 1996.

Ten krok usuwania z L przed kontynuowaniem rekurencji faktycznie poprawia algorytm, ponieważ usuwa on już dodany X z puli podstawowych kandydatów. Zawsze będzie działał, ponieważ jest równoważny z istniejącym algorytmem, a także będzie działał dla wyższych wymiarów.$X$$L$$X$

$MSW(L,B^{\prime\prime})$$X \in L$$X \in B^{\prime\prime}$$B^\prime$$X$$B \subseteq MSW(L,B)$

$X$