Reducing the Granularity of a Map

You've got this database of place coordinates, but find that two or more places are "too" close from each other.
For instance, you want to make sure that no 2 places are closer than d mile(s) from each other.
The problem is to find the minimum set of nodes to remove in order to satisfy the restriction.

While it is easy to visualize a solution for a graph of small size, it can quickly get complicated.
Consider these 3 places.

How do you decide which node(s) to remove in order to maintain the restriction that d > 3 for all pairs of points?
There clearly are 3 possibilities:

• Remove red point
• Remove black and green points
• Remove all 3 points

The good news is that this is a well known optimization problem: the Independent Set problem.
The bad news is that it is NP-hard.
A simpler problem that can be solved with a greedy algorithm is finding a maximal set.
Given two nodes A and B such that distance(A, B) < k, remove the node with the least neighbors.
In this algorithm, the map is simply a graph where there is an edge between two nodes if they are sufficiently close from each other (if the two locations are neighbors).

loop map as place1:
loop map as place2:
  if place1 != place2 and
     distance(place1, place2) < k:
    if neighbors(place1) > neighbors(place2):
      discard(place2)
    else:
      discard(place1)

Of course, any domain knowledge should be exploited.
For instance, if the map represents the biggest cities in country X, then the population size of each location should be taken into account before discarding a node.