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

17

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

( BL jest podstawa z L , jeśli B jest minimalny, tak że B=L podstawę, ma najwyżej trzy elementy, na ogół w kulki w Rd 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= , zwróć B .
  2. W przeciwnym razie wybierz XL losowo.
  3. Niech .BMSW(L{X},B)
  4. Jeżeli następnie powrócić B ' .XBB
  5. W przeciwnym przypadku powrót , w którym B " stanowi podstawę B '{ X } .MSW(L,B)BB{X}

Używane jako do obliczenia podstawy L .MSW(L,)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.


Moje pytanie: Dlaczego ta nieprawidłowa wersja algorytmu najwyraźniej podaje tutaj prawidłowe odpowiedzi? Czy to zawsze (możliwe) działa? Jeśli tak, to czy dotyczy to również wyższych wymiarów?


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):BMSW(L,B)a,b,c,d,ea,b,e

Disks a, b, c, d, e

możemy mieć ; i pamiętać, że e c , d :MSW({c,d},{a,b,e})={c,d}ec,d

the smallest enclosing circle of c and d does not contain e

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(,{a,b,e})={a,b,e}
  • Zauważmy, że XB
  • Niech więc będzie podstawą B { X } = { a , b , c , e }BB{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 XB
  • Niech więc będzie podstawą B { X } = { b , c , d }BB{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 LL
L

  1. Niech B .
  2. Losuj L losowy.
  3. Dla każdego w LXL :
  4.   Jeśli XB :
  5.     Niech będzie podstawą B { X }BB{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 BBB .

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.

Robin Houston
źródło
Po pierwsze, w wierszu „Wejście: ...” „Myślę, że chcesz” (z L) „zamiast” (z B) ”. Po drugie, zwracając MSW (L- {X}, B '') zamiast MSW (L, B ''), twoja podstawa B '' jest zdefiniowana jako podstawa [B 'unii {X}], więc X jest nadal zapewnione do pokrycia przez MSW (L- {X}, B ''), nawet jeśli usunąłeś go z zestawu.
JimN
Nie, naprawdę mam na myśli „(z B)” i B niekoniecznie jest podzbiorem L w wywołaniach rekurencyjnych. Elementy BL niekoniecznie są objęte MSW (L, B), jak w tym przykładzie bl.ocks.org/robinhouston/c4c9dffbe8bd069028cad8b8760f392c gdzie i B = { a , b , e } (Naciśnij małe przyciski ze strzałkami, aby przejść przez obliczenia.)L={a,b,c,d}B={a,b,e}
Robin Houston,

Odpowiedzi:

1

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.XLX

MSW(L,B)XLXBBXBMSW(L,B)

X

Larry B.
źródło
To nieprawda bM.S.W.(L.,b)ogólnie. Spójrz na przykład podany w moim komentarzu do pytania.
Robin Houston,
Na ogół nie jest to prawdą Xb, z tego powodu! Miałeś na myśliXb? Podejrzewam, że jeśli spróbujesz dokładniej wyjaśnić swój argument, zobaczysz, że to nie działa.
Robin Houston,
NB. It isn’t even true in general that BMSW(L,B).
Robin Houston
I’ve added a section to the question giving a counterexample to BMSW(L,B), since several people have supposed it to be true.
Robin Houston
1
Oh, I totally missed that! B=BX. Tak, ta odpowiedź jest całkowicie błędna. Czy powinienem to usunąć?
Larry B.