Algoritmo de aproximação Pergunta, agrupamento em n pontos

Question

Então, o algoritmo que pensei, é para iterar através dos n pontos, centralizando uma bola em cada ponto, e acompanhar o ponto em que centralizamos o que mais encapsulou.Em seguida, remova os pontos encapsulados dessa bola max nós encontramos e, em seguida, iterar todos os pontos novamente.Continue até que não haja mais pontos não encapsulados.Retornar todos os centros que encontramos.

Não tenho certeza se este algoritmo está correto.O (1) Algoritmo de aproximação está em termos de O ( $ \ frac {\ delta_ {nosso}} {\ delta} $ ).O requisito é um algoritmo polinomial, que acredito que o meu é na ordem de $ n ^ {2} $ .

Eu também não tenho certeza de como provar a exatidão de um algoritmo de aproximação.

Answer 1

Há um algoritmo ainda mais simples, o algoritmo ganancioso. Este algoritmo itera através dos pontos em alguma ordem. Inicialmente, o conjunto de centros está vazio. Quando ponto $ P $ é atingido, se $ P $ está a uma distância $ 2 \ delta $ de um dos centros selecionados, então não fazemos nada. Caso contrário, adicionamos $ P $ para o conjunto de centros. A implementação ingênua deste algoritmo funciona no tempo $ O (kn) $ , que é polinomial.

Por que isso funciona? Suponha que as bolas no raio $ \ delta $ centrado nos pontos $ p_ {i_1}, \ LDOTs, p_ {i_k} $ cobrir todo o conjunto e suponha que o algoritmo acima tenha selecionado pontos $ p_ {j_1}, \ ldots, p_ {j_k} $ . Temos que mostrar que cada ponto do set está dentro da distância $ 2 \ delta $ destes pontos.

Para um ponto $ P $ , deixe $ c (p) $ denotam o ponto entre < Classe Span="Recipiente de Matemática"> $ p_ {i_1}, \ lDOTs, p_ {i_k} $ Qual é o mais próximo da $ p $ . Eu reivendo que $ c (p_ {j_a}) \ neq c (p_ {j_b}) $ para $ a \ neq B $ . De fato, por construção $ \ | p_ {j_a} -p_ {j_b} \ | > 2 \ delta $ . Mas se $ c (p_ {j_a})= c (p_ {j_b})= q $ , então $ \ | p_ {j_a} -p_ {j_b} \ | \ leq \ | p_ {j_a} -q \ | + \ | q-p_ {j_b} \ | \ leq 2 \ delta $ .

renumerar os pontos para que $ c (p_ {j_a})= p_ {i_a} $ e considere um ponto arbitrário $ P $ no conjunto. Suponha que $ c (p)= p_ {i_a} $ . Então $ \ | p-p_ {j_a} \ | \ leq \ | p-p_ {i_a} \ | + \ | p_ {i_a} -p_ {j_a} \ | \ leq 2 \ delta $ .