Círculo máximo máximo de um determinado raio

19

Eu tento encontrar uma abordagem para o seguinte problema:

Dado o conjunto de pontos e raio r , encontre o ponto central do círculo, de modo que o círculo contenha o número máximo de pontos do conjunto. O tempo de execução deve ser O ( n 2 ) .SrO(n2)

A princípio, parecia ser algo semelhante ao menor problema de círculo fechado, que facilmente pode ser resolvido em . A idéia era estabelecer um centro arbitrária e envolver todos os pontos de S . Em seguida, passo a passo, substitua o círculo para tocar nos pontos mais à esquerda / direita e reduza o círculo ao raio especificado, obviamente, isso não vai funcionar.O(n2)S

com
fonte

Respostas:

7

Não sei como resolver esse problema no tempo , mas existe um algoritmo O ( n 2 log n ) .O(n2)O(n2logn)

Seja o círculo cujo centro é s i , o i- ésimo ponto, com raio r . Não é difícil descobrir que o conjunto de pontos P = { p 0 , p 1 , , p m } possa ser delimitado por um círculo com raio r se a interseção I ( P ) de C ( p 0 ) , C ( p 1 ) , C(si)siirP={p0,p1,,pm}rI(P) não está vazio. Além disso, se I ( P ) não estiver vazio, deve haver alguns pontos em I ( P ) colocados em algum bd C ( p i ) (o limite de C ( p i ) ). Portanto, para cada C ( s i ) e cada ponto p em sua ligação, tentamos descobrir quantos círculos contêm p . A contagem máxima entre todos os p será a resposta para esse problema.C(p0),C(p1),,C(pm)I(P)I(P)bdC(pi)C(pi)C(si)ppp

Vamos examinar os pontos em . Existe um mapeamento individual entre os pontos em bd C ( s i ) e o número real em [ 0 , 2 π ) . Para cada círculo C ( s j ) , a interseção entre C ( s j ) e bd C ( s i ) pode ser representada por um intervalo [ b e g i n jbdC(si)bdC(si)[0,2π)C(sj)C(sj)bdC(si) . Portanto, para todos os círculos que não sejam C ( s i ) , há no máximo n - 1 intervalos (alguns círculos podem não se cruzar com C ( s i ) ). A contagem máxima pode ser encontrada facilmente, classificando todos os 2 ( n - 1 ) pontos finais do intervalo, varrendo-os em ordem e contando o número sobreposto atual. Para cada C ( s i ) , esta etapa pode ser realizada em O ( n log n[beginj,endj]C(si)n1C(si)2(n1)C(si) time, e existem n tais círculos, portanto, a complexidade do tempo desse algoritmo é O ( n 2 log n ) .O(nlogn)nO(n2logn)

Wu Yin
fonte
2
A disposição dos círculos pode ser construída no tempo (com alta probabilidade) usando um algoritmo incremental aleatório padrão. De fato, o tempo de execução é O ( n log n + k ) , onde k é o número de pares de círculos que se cruzam. Veja seu livro de geometria computacional favorito. O(n2)O(nlogn+k)k
1011 JeffE
2

Acho que as perguntas difíceis são saber se o círculo que você selecionou é realmente "máximo" dentro do conjunto. A única maneira de pensar para determinar isso é tentar todas as combinações possíveis dos pontos e testar o tamanho do círculo que os envolve.

Você pode reduzir o espaço de pesquisa dividindo primeiro o espaço do ponto em uma grade de células quadradas com largura 2r. Em seguida, localize a célula com a maior densidade. Como você já localizou um círculo de X pontos, pode concluir que, se um círculo existir com mais pontos, ele deverá ter pelo menos X pontos. E use isso como ponto de partida para testar as diferentes combinações dos pontos.

Se você estiver procurando apenas um conjunto de pontos que provavelmente seja o máximo, poderá reduzir ainda mais o número de combinações que precisa testar selecionando aqueles que se enquadram em uma vizinhança de células onde a densidade da vizinhança é maior que X.

Dito isto, ambas as "reduções" podem falhar e, na pior das hipóteses, você estará computando círculos para todas as combinações possíveis de pontos.

putnampp
fonte
1

O(n2)

O(n2)

2n2O(n2log(n))

O(n2)O(n2)

V+EF=2O(n2)

stack99
fonte
Se isso deve ser lido como um complemento à resposta aceita e não deve ser lido por si só (o que eu não sei, por desconhecer esse tópico), você deve ser explícito.
31515 babou