Given a radius R, find the minimal number of circles to maximize the area where the circles' center belong to a set of points P

Question

Given a list of points, P, and a radius R, find the minimum set of points P that maximizes the area. Where each point represents a circle centered at that point.

For example, given the points (3,2), (7,3), (0,-1), (5,-1), (4,1), the point (4,1) is redundant as it doesn't offer any extra area that isn't already covered by the other points.

Would some kind of backtracking solution work? Where we calculate the area of every possible combination? Ideally there's a solution that's more efficient because I'd like this to handle a large number of points.

Another example:

In this case, the answer is all points because each point contributes to the total area covered. The ones in the middle give a little bit of area highlighted in yellow.

Is there solution that can be generalized for any radius? That is, each point has their own radius.

Answer 1

If you are given n center points, you only need to consider at most n² "point of interest", including:

• The given circle centers; and
• The at most 2 circle intersection points for every pair of centers.

If a point of interest is not intersected by any circles (it must be a center point), then it represents a distinct enclosed area. Find all the circles that contain it.

Otherwise, if a point if interest is intersected by k circles, then it is adjacent to at most 2k enclosed areas. For each of those areas, find all the circles that contain it.

All of the above can be done in O(n² log n) time.

Now you have a bunch of circle sets, each of which contains the set of circles that cover some area. Assign an ID to each distinct circle set.

Then, for each circle center, construct the set of IDs for all the circle sets that its circle covers.

You have transformed your problem into a set cover problem -- your goal is to find the smallest number of center ID sets that cover all of the IDs.

As mentioned in the linked Wikipedia article, this is an NP-hard problem, but the instances you create are likely to be pretty easy.