Geek Answers Handbook

The maximum subset of points with a specific density

Suppose that the set of points S in a 2D plane is how to remove the minimum number of points from S so that the distances between any two remaining points are not less than a constant, say R.

I guess it could be NP-hard. Can anyone suggest a quick rough solution? Thank you

+4
source share
2 answers

My friend offers a reasonable solution:

Construct a graph G in which all edges are less than R. The set of deleted points coincides with the minimal vertex covering of G. The vertex cover approximation is in polynomial time.

+1
source

, . , 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
0

More articles:


All Articles