Cómo no calcular el círculo más pequeño que encierra un conjunto finito de círculos

17

Supongamos que tenemos un conjunto finito de discos en , y deseamos calcular el disco más pequeño para el que . Una forma estándar de hacer esto es utilizar el algoritmo de Matoušek, Sharir y Welzl [1] para encontrar una base de , y dejar que , el disco más pequeño que contiene . El disco puede calcularse algebraicamente utilizando el hecho de que, dado que es una base, cada disco en es tangente a .LR2DLDBLD=BBBBBB

( es una base de si es mínimo, de modo que . Una base tiene como máximo tres elementos; en general, para bolas en una base tiene como máximo elementos).BLLBB=LRdd+1

Es un algoritmo recursivo aleatorio de la siguiente manera. (Pero vea a continuación una versión iterativa, que puede ser más fácil de entender).

Procedimiento : Entrada : conjuntos finitos de discos , , donde B es una base (de B ).MSW(L,B)
LBBB

  1. Si L= , el retorno B .
  2. De lo contrario, elija XL al azar.
  3. Deje BMSW(L{X},B) .
  4. Si XB , devuelve B .
  5. De lo contrario, devuelva MSW(L,B) , donde B es una base de B{X} .

Se utiliza como MSW(L,) para calcular una base de L .

Recientemente tuve motivos para implementar este algoritmo. Después de verificar que los resultados fueron correctos en millones de casos de prueba generados aleatoriamente, noté que había cometido un error en la implementación. En el último paso, estaba devolviendo MSW(L{X},B) lugar de MSW(L,B) .

A pesar de este error, el algoritmo estaba dando las respuestas correctas.


Mi pregunta: ¿Por qué esta versión incorrecta del algoritmo aparentemente da respuestas correctas aquí? ¿Siempre funciona (probablemente)? Si es así, ¿eso también es cierto en las dimensiones superiores?


Añadido: algunas ideas falsas

Varias personas han propuesto argumentos incorrectos en el sentido de que el algoritmo modificado es trivialmente correcto, por lo que puede ser útil evitar algunos conceptos erróneos aquí. Una creencia falsa popular parece ser que . Aquí hay un contraejemplo a esa afirmación. Dados los discos como se muestra a continuación (el límite de también se muestra en rojo):un , b , c , d , esiMETROSW(L,si)un,si,C,re,miun,si,mi

Discos a, b, c, d, e

podemos tener ; y tenga en cuenta que :e c , d METROSW({C,re},{un,si,mi})={C,re}miC,re

el círculo cerrado más pequeño de cyd no contiene e

Así es como puede suceder. La primera observación es que :MSW({c},{a,b,e})={b,c}

  • Deseamos calcularMSW({c},{a,b,e})
  • ElijaX=c
  • DejeB=MSW(,{a,b,e})={a,b,e}
  • Observe queXB
  • Deje que sea ​​la base deB { X } = { a , b , c , e }BB{X}={a,b,c,e}
  • Observe queB={b,c}
  • Devuelve , que es{ b , c }MSW({c},{si,C}){si,C}

Ahora considere .MSW({c,d},{a,b,e})

  • Deseamos calcularMSW({c,d},{a,b,e})
  • ElijaX=d
  • DejeB=MSW({c},{a,b,e})={b,c}
  • Observe queXB
  • Deje que sea ​​la base deB { X } = { b ,BB{X}={b,c,d}
  • Observe queB={c,d}
  • Devuelve , que esMSW({c,d},{c,d}){c,d}

(En aras de la definición, digamos que los discos tienen radio 2 y están centrados en , , , y respectivamente.)( 30 , 5 ) ( 30 , 35 ) ( 10 , 5 )a,b,c,d,e(30,5)(30,35)(10,5)( 5 , 26(60,26)(5,26)


Añadido: una presentación iterativa

Puede ser más fácil pensar en una presentación iterativa del algoritmo. Ciertamente me resulta más fácil visualizar su comportamiento.

Entrada : una lista de discos Salida : una base deL
L

  1. Deje .B
  2. Baraja al azar.L
  3. Para cada en :XL
  4.   Si :XB
  5.     Deje que sea ​​la base de .B BB{X}
  6.     Regrese al paso 2.
  7. Volver .B

La razón por la cual el algoritmo termina, por cierto, es que el paso 5 siempre aumenta el radio de , y solo hay muchos valores posibles de finita .BBB

La versión modificada no tiene una presentación iterativa tan simple, por lo que puedo ver. (Traté de dar uno en la edición anterior de esta publicación, pero fue incorrecto y arrojó resultados incorrectos).


Referencia

[1] Jiří Matoušek, Micha Sharir y Emo Welzl. Un límite subexponencial para la programación lineal. Algorithmica, 16 (4-5): 498-516, 1996.

Robin Houston
fuente
En primer lugar, en su línea "Entrada: ..." Creo que quiere "(de L)" en lugar de "(de B)". En segundo lugar, al devolver MSW (L- {X}, B '') en lugar de MSW (L, B ''), su base B '' se define como una base de [B 'union {X}] por lo que X es todavía se aseguró de estar cubierto por MSW (L- {X}, B ''), a pesar de que lo eliminó del conjunto.
JimN
No, realmente quiero decir "(de B)" allí, y B no es necesariamente un subconjunto de L en llamadas recursivas. Los elementos de BL no están cubiertos necesariamente por MSW (L, B), como en este ejemplo bl.ocks.org/robinhouston/c4c9dffbe8bd069028cad8b8760f392c donde y (Presione los pequeños botones de flecha para recorrer el cálculo.)B = { a , b , e }L={a,b,c,d}B={a,b,e}
Robin Houston,

Respuestas:

1

Este paso de eliminar de antes de continuar la recursión en realidad mejora el algoritmo, porque elimina la ya agregada del grupo de candidatos básicos. Siempre funcionará, probablemente, porque es equivalente al algoritmo existente, y también funcionará para dimensiones superiores.L XXLX

Traza a través del algoritmo. Cuando usa , hay y . Supongamos que lo elegimos nuevamente en el paso 2. Independientemente del resultado del paso 3, siempre tendrá , porque la función recursiva tiene la invariante .X L X B B X B M S W ( L , B )MSW(L,B)XLXBBXBMSW(L,B)

En otras palabras, su mejora en los atajos de algoritmo al paso 3 en la parte donde se eligeX

Larry B.
fuente
No es cierto que en general. Eche un vistazo al ejemplo vinculado en mi comentario sobre la pregunta. BMSW(L,B)
Robin Houston el
¡Tampoco es cierto en general que , en realidad ! ¿Quiso decir ? Sospecho que si intentas explicar tu argumento más rigurosamente, verás que no funciona. XBXB
Robin Houston
NÓTESE BIEN. Ni siquiera es cierto en general que . BMSW(L,B)
Robin Houston
He agregado una sección a la pregunta que da un contraejemplo a , ya que varias personas han supuesto que es cierto. BMSW(L,B)
Robin Houston el
1
¡Oh, lo extrañé totalmente! . Sí, esta respuesta es totalmente incorrecta. ¿Debo eliminarlo? B=BX
Larry B.