Wie man nicht den kleinsten Kreis berechnet, der eine endliche Menge von Kreisen einschließt

17

Angenommen, wir haben eine endliche Menge L von Platten in R2 und möchten die kleinste Platte berechnen, Dfür die LD . Ein Standard - Weg , dies zu tun , ist der Algorithmus von Matoušek, Sharir und Welzl [1] zu verwenden , um eine Basis zu finden B von L , und lassen D=B , die kleinste Platte enthält B . Die Scheibe B kann algebraisch unter Verwendung der Tatsache berechnet werden , dass, da B eine Basis ist, wobei jede Scheibe in B tangential zu B.

( BL ist eine Basis von L , wenn B minimal ist , so dass B=L Eine Basis hat höchstens drei Elemente,. Im allgemeinen für die Kugeln in Rd eine Basis hat höchstens d+1 . Elemente)

Es ist ein randomisierter rekursiver Algorithmus wie folgt. (Nachfolgend finden Sie eine iterative Version, die möglicherweise leichter zu verstehen ist.)

Verfahren : MSW(L,B)
Eingabe : Finite Sätze von Scheiben L , B , wobei B eine Basis (von ist B ).

  1. Wenn L= , geben Sie B .
  2. Andernfalls wählen Sie XL zufällig.
  3. Lassen BMSW(L{X},B) .
  4. Wenn XB dann zurück B .
  5. Andernfalls zurückkehren , in denen B " eine Basis ist , B '{ X } .MSW(L,B)BB{X}

Wird als eine Basis zu berechnen L .MSW(L,)L

Vor kurzem hatte ich Grund, diesen Algorithmus zu implementieren. Nachdem ich in Millionen zufällig generierten Testfällen die Richtigkeit der Ergebnisse überprüft hatte, stellte ich fest, dass ich einen Fehler in der Implementierung gemacht hatte. Im letzten Schritt habe ich und nicht M S W ( L , B " ) zurückgegeben .MSW(L{X},B)MSW(L,B)

Trotz dieses Fehlers gab der Algorithmus die richtigen Antworten.


Meine Frage: Warum gibt diese falsche Version des Algorithmus anscheinend hier richtige Antworten? Funktioniert es immer (nachweislich)? Wenn ja, gilt das auch für höhere Dimensionen?


Hinzugefügt: einige Missverständnisse

Einige Leute haben falsche Argumente vorgeschlagen, um den modifizierten Algorithmus für trivial korrekt zu halten. Daher kann es nützlich sein, hier einige Missverständnisse zu vermeiden. Ein populärer falscher Glaube scheint zu sein , dass . Hier ist ein Gegenbeispiel zu dieser Behauptung. Gegeben Scheiben ein , b , c , d , e , wie nachstehend (die Grenze des a , b , e wird auch in rot dargestellt):BMSW(L,B)a,b,c,d,ea,b,e

Disks a, b, c, d, e

wir können ; und beachten Sie, dass 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

So kann es passieren. Die erste Beobachtung ist , daß :MSW({c},{a,b,e})={b,c}

  • Wir wünschen berechnen MSW({c},{a,b,e})
  • Wähle X=c
  • Sei B=MSW(,{a,b,e})={a,b,e}
  • Beachten Sie, dass XB
  • So lassen eine Basis von B '{ X } = { a , b , c , e }BB{X}={a,b,c,e}
  • Beachten Sie, dass B={b,c}
  • Gib , das ist { b , c }MSW({c},{b,c}){b,c}

Betrachten wir nun .MSW({c,d},{a,b,e})

  • Wir wollen M S W berechnen ( { c , d } , { a , b , e } )MSW({c,d},{a,b,e})
  • Wähle X=d
  • Lassen B=MSW({c},{a,b,e})={b,c}
  • Beachten Sie, dass XB
  • Sei also eine Basis von B '{ X } = { b , c , d }BB{X}={b,c,d}
  • Beachten Sie, dass B={c,d}
  • Gib , das ist { c , d }MSW({c,d},{c,d}){c,d}

(Nehmen wir der Bestimmtheit halber an, die Scheiben alle den Radius 2 und sind zentriert bei ( 30 , 5 ) , ( 30 , 35 ) , ( 10 , 5 ) , ( 60 , 26 ) bzw. ( 5 , 26 ) .)a,b,c,d,e(30,5)(30,35)(10,5)(60,26)(5,26)


Hinzugefügt: eine iterative Präsentation

Es kann einfacher sein, über eine iterative Darstellung des Algorithmus nachzudenken. Ich finde es auf jeden Fall einfacher, sein Verhalten zu visualisieren.

Eingabe : Eine Liste von Platten Ausgabe : Eine Basis von LL
L

  1. Sei .B
  2. Mische zufällig.L
  3. Für jedes in L :XL
  4.   Wenn :XB
  5.     Sei eine Basis von B { X } .BB{X}
  6.     Fahren Sie mit Schritt 2 fort.
  7. Return .B

Der Grund der Algorithmus endet, nebenbei bemerkt, ist , dass Schritt 5 immer den Radius erhöht - und es gibt nur endlich viele mögliche Werte von B .BB

Die modifizierte Version hat meines Erachtens keine so einfache iterative Darstellung. (Ich habe versucht, in der vorherigen Bearbeitung einen zu diesem Beitrag hinzuzufügen, aber er war falsch - und habe falsche Ergebnisse geliefert.)


Referenz

[1] Jiří Matoušek, Micha Sharir und Emo Welzl. Eine subexponentielle Grenze für die lineare Programmierung. Algorithmica, 16 (4-5): 498–516, 1996.

Robin Houston
quelle
Erstens, in Ihrer Zeile "Input: ..." denke ich, dass Sie "(von L)" statt "(von B)" wollen. Zweitens, wenn Sie MSW (L- {X}, B '') anstelle von MSW (L, B '') zurückgeben, wird Ihre Basis B '' als Basis von [B 'union {X}] definiert, also ist X Es ist weiterhin sichergestellt, dass es von MSW (L- {X}, B '') abgedeckt wird, obwohl Sie es aus dem Satz entfernt haben.
JimN
Nein, ich meine dort wirklich "(von B)" und B ist nicht notwendigerweise eine Teilmenge von L in rekursiven Aufrufen. Elemente von BL werden nicht unbedingt von MSW (L, B) abgedeckt, wie in diesem Beispiel bl.ocks.org/robinhouston/c4c9dffbe8bd069028cad8b8760f392c wobei und B = { a , b , e } (Drücken Sie die kleinen Pfeiltasten, um die Berechnung zu durchlaufen.)L={a,b,c,d}B={a,b,e}
Robin Houston

Antworten:

1

Dieser Schritt des Entfernens von aus L, bevor die Rekursion fortgesetzt wird, verbessert den Algorithmus tatsächlich, da das bereits hinzugefügte X aus dem Pool der Basiskandidaten entfernt wird. Es wird nachweislich immer funktionieren, da es dem vorhandenen Algorithmus entspricht und auch für höhere Dimensionen funktioniert.XLX

Verfolgen Sie den Algorithmus. Wenn Sie , gibt es X L und X B MSW(L,B)XLXB . Angenommen, wir haben es in Schritt 2 erneut gewählt. Unabhängig vom Ergebnis von Schritt 3 hat immer X , da die rekursive Funktion die Invariante B M hatBX .BMSW(L,B)

Mit anderen Worten, Ihre Verbesserung des Algorithmus führt Sie zu Schritt 3 in dem Teil, in dem ausgewählt ist.X

Larry B.
quelle
Es ist nicht so , daß im Allgemeinen. Schauen Sie sich das Beispiel an, das in meinem Kommentar zur Frage verlinkt ist. BMSW(L,B)
Robin Houston
XBXB
BMSW(L,B)
BMSW(L,B)
1
B=BX