近似算法问题，在n点上群集

Question

所以我想到的算法是迭代N点，以每个点居中球，并跟踪我们以封装最多点封装的点。然后从我们发现的这个Max球中删除封装的点，然后再次迭代所有点。继续，直到不再封装任何点。返回我们找到的所有中心。

我不确定此算法是否正确。o（1）近似算法符合O（ $ \ frac {\ delta_ {uss} {\ delta} $ ）。要求是一种多项式算法，我认为我的是 $ n ^ {2} $ 的顺序。

我也不确定如何证明近似算法的正确性。

Answer 1

有更简单的算法，贪婪算法。此算法以某种顺序迭代点。最初，一组中心是空的。当点 $ p $ 时，如果 $ p $ 在距离 $ 2 \ Delta $ 其中一个选定中心，然后我们什么都不做。否则，我们将 $ p $ 添加到该集中。这个算法的天真实现在时间 $ o（kn）$ ，这是多项式。

为什么这项工作？假设在半径 $ \ delta $ 以 $ p_ {i_1}，\ ldots，p_ {i_k}为中心的球$ 覆盖整个集合，并假设上面的算法已选择点 $ p_ {j_1}，\ ldots，p_ {j_k} $ 。我们必须展示集合中的每个点都在距离 $ 2 \ delta $ 中的距离

对于一个点 $ p $ ，让 $ c（p）$ 表示<跨越类=“math-container”> $ p_ {i_1}，\ ldots，p_ {i_k} $ 最接近 $ p $ 。 我声称 $ c（p_ {j_a}）\ neq c（p_ {j_b}）$ for $ a \ neq B $ 。的确，通过施工 $ \ | p_ {j_a} -p_ {j_b} \ | > 2 \ delta $ 。但是，如果 $ c（p_ {j_a}）= c（p_ {j_b}）= c（p_ {j_b}）= q $ ，则 $ \ | p_ {j_a} -p_ {j_b} \ | \ leq \ | p_ {j_a} -q \ | + \ | q-p_ {j_b} \ | \ Leq 2 \ Delta $ 。

重新编号点，使 $ c（p_ {j_a}）= p_ {i_a} $ ，并考虑任意点 $ p $ 在集合中。假设 $ c（p）= p_ {i_a} $ 。然后 $ \ | p-p_ {j_a} \ | \ leq \ | p-p_ {i_a} \ | + | P_ {i_a} -p_ {j_a} \ | \ Leq 2 \ Delta $ 。