Approximation d'algorithme Question, regroupement sur n points

Question

Ainsi, l'algorithme que j'ai pensé, est de parcourir les n points, de centrer une balle à chaque point et de garder une trace du point où nous avons consacré ce qui a encapsulé le plus de points.Ensuite, retirez les points encapsulés de cette balle max que nous avons trouvée, puis itérale à nouveau à nouveau tous les points.Continuez jusqu'à ce qu'il n'y ait plus de points non encapsulés.Retour Tous les centres que nous avons trouvés.

Je ne sais pas si cet algorithme est correct.O (1) L'algorithme d'approximation est en termes d'O ( $ \ frac {\ delta_ {nôtre}}} {\ delta} $ ).L'exigence est un algorithme polynomial, que je crois que le mien est dans l'ordre de $ n ^ {2} $ .

Je ne sais pas non plus comment prouver l'exactitude d'un algorithme d'approximation non plus.

Answer 1

Il y a un algorithme encore plus simple, l'algorithme gourmand. Cet algorithme itière à travers les points dans certains ordres. Initialement, l'ensemble des centres est vide. Lorsque le point $ p $ est atteint, si $ p $ est dans la distance 2 \ delta $ de l'un des centres sélectionnés, nous ne faisons rien. Sinon, nous ajoutons $ p $ à l'ensemble des centres. La mise en œuvre naïve de cet algorithme fonctionne dans le temps $ o (kn) $ , qui est polynomial.

Pourquoi cela fonctionne-t-il? Supposons que les balles au rayon $ \ delta $ centré sur les points $ p_ {i_1}, \ ldots, p_ {i_k} $ Couvre l'ensemble de l'ensemble et supposez que l'algorithme ci-dessus ait sélectionné les points sélectionnés $ p_ {j_1}, \ ldots, p_ {j_k} $ . Nous devons montrer que chaque point de l'ensemble est dans la distance de distance 2 \ delta $ de ces points.

pour un point $ p $ , let $ c (p) $ désigne le point par rapport à < span class="math-conteneur"> $ p_ {i_1}, \ ldots, p_ {i_k} $ qui est le plus proche de $ p $ . Je prétend que $ c (p_ {j_a}) \ neq c (p_ {j_b}) $ pour $ a \ neq B $ . En effet, par construction $ \ | p_ {j_a} -p_ {j_b} \ | > 2 \ delta $ . Mais si $ c (p_ {j_a})= C (p_ {j_b})= q $ , alors $ \ | p_ {j_a} -p_ {j_b} \ | \ Leq \ | p_ {j_a} -q \ | + \ | q-p_ {j_b} \ | \ Leq 2 \ delta $ .

Renumérotez les points de sorte que $ c (p_ {j_a})= p_ {i_a} $ et envisagez un point de point $ p $ dans l'ensemble. Supposons que $ C (p)= p_ {i_a} $ . Alors $ \ | p-p_ {j_a} \ | \ Leq \ | p-p_ {i_a} \ | + \ | p_ {i_a} -p_ {j_a} \ | \ Leq 2 \ delta $ .