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

Angenommen, wir haben eine endliche Menge $L$ von Platten in $\mathbb{R}^2$ und möchten die kleinste Platte berechnen, $D$für die $\bigcup L\subseteq D$ . 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=\langle B\rangle$ , die kleinste Platte enthält $\bigcup B$ . Die Scheibe $\langle B\rangle$ kann algebraisch unter Verwendung der Tatsache berechnet werden , dass, da $B$ eine Basis ist, wobei jede Scheibe in $B$ tangential zu $\langle B\rangle$.

( $B\subseteq L$ ist eine Basis von $L$ , wenn $B$ minimal ist , so dass $\langle B\rangle=\langle L\rangle$ Eine Basis hat höchstens drei Elemente,. Im allgemeinen für die Kugeln in $\mathbb{R}^d$ 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=\varnothing$ , geben Sie $B$ .
2. Andernfalls wählen Sie $X\in L$ zufällig.
3. Lassen $B'\leftarrow MSW(L-\{X\}, B)$ .
4. Wenn $X\subseteq\langle B'\rangle$ dann zurück $B'$ .
5. Andernfalls zurückkehren , in denen B " eine Basis ist , B ' ∪ { X } .$MSW(L, B'')$$B''$$B'\cup\{X\}$

Wird als eine Basis zu berechnen L .$MSW(L, \varnothing)$$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.

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):$B\subseteq\langle MSW(L, B)\rangle$$a,b,c,d,e$$\langle a,b,e\rangle$

wir können ; und beachten Sie, dass e ∉ ⟨ c , d ⟩ :$MSW(\{c, d\}, \{a,b,e\})=\{c,d\}$$e\notin\langle c,d\rangle$

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(\varnothing, \{a,b,e\}) = \{a,b,e\}$
• Beachten Sie, dass $X\notin\langle B'\rangle$
• So lassen eine Basis von B ' ∪ { X } = { a , b , c , e $B''$$B'\cup\{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 $X\notin\langle B'\rangle$
• Sei also eine Basis von B ' ∪ { X } = { b , c , d $B''$$B'\cup\{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 $L$
$L$

1. Sei .$B\leftarrow\varnothing$
2. Mische zufällig.$L$
3. Für jedes in L :$X$$L$
4.   Wenn :$X\notin\langle B\rangle$
5.     Sei eine Basis von B ∪ { X } .$B$$B\cup\{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 .$\langle B\rangle$$B$

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.

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.$X$$L$$X$

Verfolgen Sie den Algorithmus. Wenn Sie , gibt es X ∈ L und X ∈ B ′ $MSW(L,B^{\prime\prime})$$X \in L$$X \in B^{\prime\prime}$ . 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 ⊆ $B^\prime$$X$ .$B \subseteq MSW(L,B)$

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