Comment ne pas calculer le plus petit cercle entourant un ensemble fini de cercles

Supposons que nous ayons un ensemble fini $L$ de disques en $\mathbb{R}^2$ , et nous souhaitons calculer le plus petit disque $D$ pour lequel $\bigcup L\subseteq D$ . Une manière standard de le faire est d'utiliser l'algorithme de Matoušek, Sharir et Welzl [1] pour trouver une base $B$ de $L$ , et que $D=\langle B\rangle$ , le plus petit disque contenant $\bigcup B$ . Le disque $\langle B\rangle$ peut être calculé algébriquement utilisant le fait que, étant donné que $B$ est une base, chaque disque $B$ est tangente à $\langle B\rangle$.

( $B\subseteq L$ est une base de $L$ si $B$ est minimale telle que $\langle B\rangle=\langle L\rangle$ base A comporte au plus trois éléments;. En général pour les boules dans $\mathbb{R}^d$ une base a au plus $d+1$ . Éléments)

Il s'agit d'un algorithme récursif randomisé comme suit. (Mais voir ci-dessous pour une version itérative, qui peut être plus facile à comprendre.)

Procédure : $MSW(L, B)$
Entrée : ensembles finis de disques $L$ , $B$ , où $B$ est une base (de $B$ ).

1. Si $L=\varnothing$ , retour $B$ .
2. Sinon, choisissez $X\in L$ au hasard.
3. Soit $B'\leftarrow MSW(L-\{X\}, B)$ .
4. Si $X\subseteq\langle B'\rangle$ puis retour $B'$ .
5. Sinon, retournez , où B ″ est une base de B ′ ∪ { X } .$MSW(L, B'')$$B''$$B'\cup\{X\}$

Utilisé comme pour calculer une base de L .$MSW(L, \varnothing)$$L$

Récemment, j'ai eu à implémenter cet algorithme. Après avoir vérifié que les résultats étaient corrects dans des millions de cas de test générés aléatoirement, j'ai remarqué que j'avais fait une erreur dans l'implémentation. Dans la dernière étape, je retournais plutôt que M S W ( L , B ″ ) .$MSW(L-\{X\}, B'')$$MSW(L, B'')$

Malgré cette erreur, l'algorithme donnait les bonnes réponses.

Ajouté: quelques idées fausses

Plusieurs personnes ont proposé des arguments incorrects à l'effet que l'algorithme modifié est trivialement correct, il peut donc être utile de prévenir certaines idées fausses ici. Une fausse croyance populaire semble être que . Voici un contre-exemple à cette affirmation. Compte tenu de disques a , b , c , d , e comme ci - dessous (la limite de ⟨ a , b , e ⟩ est également montré en rouge):$B\subseteq\langle MSW(L, B)\rangle$$a,b,c,d,e$$\langle a,b,e\rangle$

on peut avoir ; et notez que e ∉ ⟨ c , d ⟩ :$MSW(\{c, d\}, \{a,b,e\})=\{c,d\}$$e\notin\langle c,d\rangle$

Voici comment cela peut se produire. La première observation est que :$MSW(\{c\},\{a,b,e\})=\{b,c\}$

• Nous souhaitons calculer $MSW(\{c\},\{a,b,e\})$
• Choisissez $X = c$
• Soit $B' = MSW(\varnothing, \{a,b,e\}) = \{a,b,e\}$
• Remarquons que $X\notin\langle B'\rangle$
• Soit donc une base de B ′ ∪ { X } = { a , b , c , e $B''$$B'\cup\{X\} = \{a,b,c,e\}$
• Observez que $B''=\{b,c\}$
• Renvoie , qui est { b , c $MSW(\{c\}, \{b,c\})$$\{b,c\}$

Considérons maintenant .$MSW(\{c, d\}, \{a,b,e\})$

• Nous souhaitons calculer $MSW(\{c, d\}, \{a,b,e\})$
• Choisissez $X=d$
• Soit $B' = MSW(\{c\}, \{a,b,e\}) = \{b,c\}$
• Remarquons que $X\notin\langle B'\rangle$
• Soit donc une base de B ′ ∪ { X } = { b , c , d $B''$$B'\cup\{X\} = \{b,c,d\}$
• Observez que $B''=\{c,d\}$
• Renvoie , qui est { c , d $MSW(\{c,d\}, \{c,d\})$$\{c,d\}$

(Par souci de clarté, disons que les disques ont tous un rayon 2 et sont centrés sur ( 30 , 5 ) , ( 30 , 35 ) , ( 10 , 5 ) , ( 60 , 26 ) et ( 5 , 26 ) respectivement.)$a,b,c,d,e$$(30,5)$$(30,35)$$(10, 5)$$(60, 26)$$(5, 26)$

Ajouté: une présentation itérative

Il peut être plus facile de penser à une présentation itérative de l'algorithme. Je trouve certainement plus facile de visualiser son comportement.

Entrée : une liste de disques Sortie : une base $L$
$L$

1. Soit .$B\leftarrow\varnothing$
2. Mélangez au hasard.$L$
3. Pour chaque dans L :$X$$L$
4.   Si :$X\notin\langle B\rangle$
5.     Soit une base de B ∪ { X } .$B$$B\cup\{X\}$
6.     Revenez à l'étape 2.
7. Retour .$B$

La raison pour laquelle l'algorithme se termine, soit dit en passant, est que l' étape 5 augmente toujours le rayon de - et il n'y a que de nombreuses valeurs possibles finiment de B .$\langle B\rangle$$B$

La version modifiée n'a pas une présentation itérative aussi simple que je sache. (J'ai essayé d'en donner un dans l'édition précédente de ce post, mais c'était faux - et j'ai donné des résultats incorrects.)

Référence

[1] Jiří Matoušek, Micha Sharir et Emo Welzl. Une limite sous-exponentielle pour la programmation linéaire. Algorithmica, 16 (4-5): 498-516, 1996.

Cette étape de suppression de $X$ de avant de continuer la récursivité améliore réellement l'algorithme, car elle supprime le X déjà ajouté du pool de candidats de base. Cela fonctionnera toujours, de manière prouvée, car il est équivalent à l'algorithme existant, et il fonctionnera également pour des dimensions plus élevées.$L$$X$

Suivez l'algorithme. Lorsque vous utilisez , il y a X ∈ L et X ∈ B ′ ′ . Supposons que nous l'avons choisi à nouveau à l'étape 2. Quel que soit le résultat de l'étape 3, B ′ aura toujours X , car la fonction récursive a l'invariant B ⊆ $MSW(L,B^{\prime\prime})$$X \in L$$X \in B^{\prime\prime}$$B^\prime$$X$ .$B \subseteq MSW(L,B)$

En d'autres termes, votre amélioration des raccourcis de l'algorithme à l'étape 3 dans la partie où est choisi.$X$