Approssimation Algorithm Domanda, raggruppamento su n punti

Question

Quindi l'algoritmo di cui ho pensato, è quello di iterare attraverso i punti N, centrare una palla ad ogni punto, e tenere traccia del punto in cui abbiamo centrato quello che incapsò il maggior numero di punti.Quindi rimuovere i punti incapsulati da questa palla massima che abbiamo trovato, quindi iterano di nuovo tutti i punti.Continua fino a quando non ci sono più punti non incapsulati.Restituire tutti i centri che abbiamo trovato.

Non sono sicuro se questo algoritmo è corretto.O (1) L'algoritmo di approssimazione è in termini di o ( $ \ frac {\ delta_ {i nostri}} {\ delta} $ ).Il requisito è un algoritmo polinomiale, che credo che il mio sia nell'ordine di $ n ^ {2} $ .

Non sono nemmeno sicuro di come dimostrare la correttezza di un algoritmo di approssimazione.

Answer 1

C'è un algoritmo ancora più semplice, l'algoritmo avido. Questo algoritmo itera attraverso i punti in qualche ordine. Inizialmente il set di centri è vuoto. Quando viene raggiunto il punto $ P $ , se $ p $ è a distanza $ 2 \ Delta $ di uno dei centri selezionati, allora non facciamo nulla. Altrimenti, aggiungiamo $ p $ al set di centri. L'implementazione ingenua di questo algoritmo funziona in tempo $ o (kn) $ , che è polinomiale.

Perché questo funziona? Supponiamo che le palle al raggio $ \ delta $ centrato sui punti $ p_ {i_1}, \ ldots, p_ {i_k} $ Coprire l'intero set e supponiamo che l'algoritmo sopra abbia punti selezionati $ p_ {j_1}, \ ldots, p_ {j_k} $ . Dobbiamo dimostrare che ogni punto nel set è a distanza $ 2 \ delta $ di questi punti.

per un punto $ p $ , let $ c (P) $ Denicare il punto tra $ p_ {i_1}, \ ldots, p_ {i_k} $ che è più vicino a $ p $ . Rivendico che $ c (p_ {j_a}) \ neq c (p_ {j_b}) $ per $ a \ neq B $ . Infatti, per costruzione $ \ | p_ {j_a} -p_ {j_b} \ | | > 2 \ delta $ . Ma se $ c (p_ {j_a})= c (p_ {j_b})= q $ , quindi $ \ | p_ {j_a} -p_ {j_b} \ | | \ leq \ | p_ {j_a} -q \ | + \ | q-p_ {j_b} \ | \ leq 2 \ delta $ .

Rinumera i punti in modo che $ c (p_ {j_a})= p_ {i_a} $ e considerare un punto arbitrario $ P $ nel set. Supponiamo che $ c (p)= p_ {i_a} $ . Quindi $ \ | P-P_ {J_A} \ | \ leq \ | p-p_ {i_a} \ | | + \ | p_ {i_a} -p_ {j_a} \ | \ leq 2 \ delta $ .