具有特定密度的点的最大子集

Question

假设在二维平面上有一组点S，如何从S中移除最少数量的点，使得剩余点之间的距离不小于一个常数R。

我猜这可能是NP难问题。有人能提供一个快速的近似解决方案吗？谢谢！

- GilbertLee

---

如果只有两个点且它们之间的距离小于R，是否会导致0个点？ - Striker

@Striker 减去1分。你现在只剩下1分，而且没有比R更接近的其他点了。 - Klas Lindbäck

@Striker 我也这么认为。应该剩下一个空集。 - GilbertLee

@KlasLindbäck 这很有道理。 - GilbertLee

@GilbertLee 只是想澄清一下，你是在问如何做到这一点？还是在问这个算法的复杂度是多少？ - Striker

Answer 1

我的朋友建议一个合理的解决方案：

构建一个图G，其中所有边长均小于R。需要被移除的点集与图G的最小顶点覆盖相同。顶点覆盖的近似算法可以在多项式时间内完成。

- GilbertLee

---

是的，我刚写这个。这个近似算法是2-近似，还不错，但是顶点覆盖问题在解决方案规模上也是固定参数可解的，所以只要需要删除的顶点数量较少，可以对相当大的实例进行精确求解。 - j_random_hacker

@j_random_hacker 你们俩都很厉害 - GilbertLee

Answer 2

这个算法速度快，但不一定是最小点数。请记住，在删除或禁用一个点时，循环应该处理对集合S的更改。

 For each Point P1 in S
 {
       For each Point P2 after P1 in S 
       {
             If (square(P1.x - P2.x) + square(P1.y - P2.y) < square(R) )
             {
                   remove (P2)
             }
       }
 }

对于最小但昂贵的：

use double loop to store each P2 closest to P1
example: array [P1][P2]

 Sort array based on size of array [P1].numOfElements ()
 such that largest is at the top

 now remove top element P from set S 
 and in  array P1
 and all subsequent P in P2 of all P1

  If P2 is empty for any element X in P1 then remove it

  Remove the next top element and do the process again until array is empty

  Resulting set is the answer for minimum points

- Striker