The only thing I can think of would be to, while putting the in edges, create a second set of weighted edges between points closer than 2d apart, with weights equal to the area of the intersection of circles of radius d centered that distance apart, and then you need a dominating set of the first graph that minimizes the sum of weights of edges in the weighted set of which both endpoints are in the set.
And it can be different, for example, if this is your graph:
1 2
\ /
\ /
3--4
/ \
/ \
5 6
(the lines indicate pairs of points within d of each other)
would {3, 4} be an acceptable solution? (note that given your second condition, this isn't an optimal solution, but would it work?) If you took them iteratively, removing either would remove the other, and you would have to use {2, 3, 6} or {1, 4, 5} to get all the points. This problem, the independant dominating set, is a little different although still well known. |
