Pregunta de aproximación del algoritmo, agrupamiento en n puntos

Question

Por lo tanto, el algoritmo que pensé, es iterar a través de los puntos N, centrando en una bola en cada punto, y realizando un seguimiento del punto en el que centramos que encapsulaba la mayoría de los puntos.Luego, retire los puntos encapsulados de esta bola máxima que encontramos, luego le duele a través de todos los puntos nuevamente.Continúe hasta que ya no haya puntos no encapsulados.Devuelve todos los centros que encontramos.

No estoy seguro de si este algoritmo es correcto.O (1) El algoritmo de aproximación está en términos de O ( $ \ frac {\ delta_ {uals}} {\ delta} $ ).El requisito es un algoritmo polinomio, que creo que la mía está en el orden de $ n ^ {2} $ .

No estoy seguro de cómo probar la exactitud de un algoritmo de aproximación.

Answer 1

Hay un algoritmo aún más sencillo, el algoritmo codicioso. Este algoritmo uerma a través de los puntos en algún orden. Inicialmente, el conjunto de centros está vacío. Cuando se alcanza el punto $ P $ , si $ p $ está a distancia $ 2 \ Delta $ de uno de los centros seleccionados, entonces no hacemos nada. De lo contrario, agregamos $ p $ al conjunto de centros. La implementación ingenua de este algoritmo se ejecuta en el tiempo $ O (kN) $ , que es polinomial.

¿Por qué este funciona? Supongamos que las bolas en el radio $ \ Delta $ centrado en los puntos $ p_ {i_1}, \ ldots, p_ {i_k} $ Cubra todo el conjunto, y suponga que el algoritmo anterior ha seleccionado puntos $ p_ {j_1}, \ ldots, p_ {j_k} $ . Tenemos que mostrar que cada punto del conjunto está a distancia $ 2 \ Delta $ de estos puntos.

Para un punto $ p $ , deja $ c (p) $ denota el punto entre < span class="math-contenedor"> $ p_ {i_1}, \ ldots, p_ {i_k} $ que está más cerca de $ P $ . Afirmo que $ c (p_ {j_a}) \ neq c (p_ {j_b}) $ para $ a \ neq B $ . De hecho, por construcción $ \ | p_ {j_a} -p_ {j_b} \ | > 2 \ Delta $ . Pero si $ c (p_ {j_a})= C (p_ {j_b})= Q $ , luego $ \ | p_ {j_a} -p_ {j_b} \ | \ leq \ | p_ {j_a} -q \ | + \ | Q-P_ {J_B} \ | \ leq 2 \ delta $ .

Renumber los puntos para que $ c (p_ {j_a})= p_ {i_A} $ , y considere un punto arbitrario $ P $ en el set. Supongamos que $ c (p)= p_ {i_A} $ . Luego $ \ | p-p_ {j_a} \ | \ leq \ | p-p_ {i_a} \ | + \ | p_ {i_a} -p_ {j_a} \ | \ leq 2 \ delta $ .