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

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 ) .$S$$r$$O(n^2)$

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(n^2)$$S$

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

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(s_i)$$s_i$$i$$r$$P = \{p_0, p_1, \ldots, p_m\}$$r$$I(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(p_0), C(p_1), \ldots, C(p_m)$$I(P)$$I(P)$$\textbf{bd}C(p_i)$$C(p_i)$$C(s_i)$$p$$p$$p$

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 $\textbf{bd}C(s_i)$$\textbf{bd}C(s_i)$$[0, 2\pi)$$C(s_j)$$C(s_j)$$\textbf{bd}C(s_i)$ . 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 $[begin_j, end_j]$$C(s_i)$$n-1$$C(s_i)$$2(n-1)$$C(s_i)$ time, e existem n tais círculos, portanto, a complexidade do tempo desse algoritmo é O ( n 2 log n ) .$O(n\log n)$$n$$O(n^2\log n)$

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.

$O(n^2)$

$O(n^2)$

$2n^2$$O(n^2log(n))$

$O(n^2)$$O(n^2)$

$V + E - F = 2$$O(n^2)$