Como não calcular o menor círculo que envolve um conjunto finito de círculos

17

Suponha que temos um conjunto finito L de discos em , e queremos calcular o menor disco para o qual . Uma forma normal de fazer isto é a utilização do algoritmo de MATOUSEK, Sharir e Welzl [1] para encontrar uma base do , e deixar , o menor disco contendo . O disco pode ser computado algebricamente usando o fato de que, como é uma base, cada disco em é tangente a .R2DLDBLD=BBBBBB

( é uma base de se é mínimo, de modo que . Uma base tem no máximo três elementos; em geral para bolas em uma base tem no máximo elementos.)BLB B = L R d d + 1LBB=LRdd+1

É um algoritmo recursivo aleatório da seguinte maneira. (Mas veja abaixo uma versão iterativa, que pode ser mais fácil de entender.)

Procedimento : Entrada : Conjuntos finitos de discos , , onde é uma base (de ).L B B BMSW(L,B)
LBBB

  1. Se , retorno .L=B
  2. Caso contrário, escolha aleatoriamente.XL
  3. Deixe .BMSW(L{X},B)
  4. Se , retorne .XBB
  5. Caso contrário, retorne MSW(L,B) , onde B é uma base de B{X} .

Usado como MSW(L,) para calcular a base de L .

Recentemente, tive motivos para implementar esse algoritmo. Depois de verificar se os resultados estavam corretos em milhões de casos de teste gerados aleatoriamente, notei que havia cometido um erro na implementação. Na última etapa, eu estava retornando MSW(L{X},B) vez de MSW(L,B) .

Apesar desse erro, o algoritmo estava dando as respostas certas.


Minha pergunta: Por que essa versão incorreta do algoritmo aparentemente fornece respostas corretas aqui? Sempre funciona (provavelmente)? Se sim, isso também é verdade em dimensões superiores?


Adicionado: alguns equívocos

Várias pessoas propuseram argumentos incorretos no sentido de que o algoritmo modificado é trivialmente correto, portanto pode ser útil evitar alguns conceitos errôneos aqui. Uma crença falsa popular parece ser que . Aqui está um contra-exemplo dessa alegação. Dados os discos como abaixo (o limite de também é mostrado em vermelho):um , b , c , d , e um , b , de e BMSW(L,B)a,b,c,d,ea,b,e

Discos a, b, c, d, e

podemos ter ; e observe que :e c , d MSW({c,d},{a,b,e})={c,d}ec,d

o menor círculo fechado de c e d não contém e

Aqui está como isso pode acontecer. A primeira observação é que :MSW({c},{a,b,e})={b,c}

  • Desejamos calcular oMSW({c},{a,b,e})
  • EscolhaX=c
  • SejaB=MSW(,{a,b,e})={a,b,e}
  • Observe queXB
  • Portanto, deixe ser uma base deB "{ X } = { um , b , c , de e }BB{X}={a,b,c,e}
  • Observe queB={b,c}
  • Retornar , que é{ b , c }MSW({c},{b,c}){b,c}

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

  • Desejamos calcular oMSW({c,d},{a,b,e})
  • EscolhaX=d
  • SejaB=MSW({c},{a,b,e})={b,c}
  • Observe queXB
  • Portanto, deixe ser uma base deB "{ X } = { b , c , d }BB{X}={b,c,d}
  • Observe queB={c,d}
  • Retornar , que é{ c , d }MSW({c,d},{c,d}){c,d}

(Por uma questão de definição, digamos que os discos todos tenham raio 2 e estejam centralizados em , , , e respectivamente.)( 30 , 5 ) ( 30 , 35 ) ( 10 , 5 ) ( 60 , 26 ) ( 5 , 26 )a,b,c,d,e(30,5)(30,35)(10,5)(60,26)(5,26)


Adicionado: uma apresentação iterativa

Pode ser mais fácil pensar em uma apresentação iterativa do algoritmo. Certamente acho mais fácil visualizar seu comportamento.

Entrada : Uma lista de discos Saída : Uma base deLL
L

  1. Deixe .B
  2. Embaralhe aleatoriamente.L
  3. Para cada em :LXL
  4.   Se :XB
  5.     Seja uma base de .BB{X}
  6.     Volte ao passo 2.
  7. Retorno .B

A razão os termina algoritmo, aliás, é que o passo 5 sempre aumenta o raio de - e há apenas um número finito de valores possíveis de B .BB

A versão modificada não tem uma apresentação iterativa tão simples, tanto quanto eu posso ver. (Tentei dar um na edição anterior deste post, mas estava errado - e deu resultados incorretos.)


Referência

[1] Jiří Matoušek, Micha Sharir e Emo Welzl. Um limite subexponencial para programação linear. Algorithmica, 16 (4-5): 498-516, 1996.

Robin Houston
fonte
Em primeiro lugar, na sua linha "Input: ..." Acho que você deseja "(de L)" em vez de "(de B)". Em segundo lugar, ao retornar MSW (L- {X}, B '') em vez de MSW (L, B ''), sua base B '' é definida como uma base da [B 'união {X}] para que X seja ainda garantiu a cobertura de MSW (L- {X}, B ''), mesmo que você o tenha removido do aparelho.
JimN
Não, eu realmente quero dizer "(de B)" lá, e B não é necessariamente um subconjunto de L em chamadas recursivas. Os elementos do BL não são necessariamente cobertos pelo MSW (L, B), como neste exemplo bl.ocks.org/robinhouston/c4c9dffbe8bd069028cad8b8760f392c em que e B = { a , b , e } (Pressione os pequenos botões de seta para avançar no cálculo.)L={a,b,c,d}B={a,b,e}
Robin Houston

Respostas:

1

Essa etapa de remoção do de L antes de continuar a recursão realmente melhora o algoritmo, porque remove o X já adicionado do pool de candidatos à base. Ele sempre funcionará, provavelmente, porque é equivalente ao algoritmo existente e também funcionará para dimensões mais altas.XLX

Rastreie o algoritmo. Quando você usa , há X L e X B . Suponha que a tenhamos escolhido novamente na etapa 2. Independentemente do resultado da etapa 3, B ' sempre terá X , porque a função recursiva possui o invariante B M S W ( L , B ) .MSW(L,B)XLXBBXBMSW(L,B)

Em outras palavras, sua melhoria nos atalhos do algoritmo para a etapa 3 na parte em que é escolhido.X

Larry B.
fonte
Não é verdade que em geral. Dê uma olhada no exemplo vinculado no meu comentário sobre a questão. BMSW(L,B)
Robin Houston
Nem é verdade que , nesse caso! Será que quis dizer X B " ? Eu suspeito que, se você tentar explicar seu argumento com mais rigor, verá que ele não funciona. XBXB
Robin Houston
NB. Nem sequer é verdadeiro, em geral, que . BMSW(L,B)
Robin Houston
Eu adicionei uma seção para a questão dando um contra-exemplo , já que várias pessoas têm suposto que seja verdade. BMSW(L,B)
Robin Houston
11
Ah, eu senti muita falta disso! . Sim, esta resposta está totalmente errada. Devo excluí-lo? B=BX
Larry B.