2

Given a list of circles (each with parameters (x,y,radius) ) I want to place another circle with a fixed radius such that it overlaps the maximum possible circles from the list of circles.

As long as the placed circle overlaps the optimal amount of circles, I don't care about the exact placement (i.e. if there are multiple possible placements with the same number of overlaps, I don't care which one is returned).

To make it a bit easier, let's asume I already have a quick way (spatial partitioning data structure or something similar) to determine circle<-> circle overlaps in general (i.e. find which circles another circle overlaps).

How can I compute the (x,y) [since radius is fixed] of the placement circle?

Bonus question:

  • How can I compute this more quickly?

Bonus Bonus question:

  • Let's say I'm happy with an approximate answer. It doesn't have to be the exact optimal value as long as it's close enough and the solution isn't obviously wrong (e.g. out of 10 circles in the list, the optimal placement would be 9 circles and the approximate solution only finds placement for 2 overlaps). Can I further improve the computation speed with this lifted restriction? Could I perhaps do this with random sampling, pick the best result, and pick the distribution of the samples in some way that guarantees a decent result?
1
  • I'm pretty sure this is one of the "hard" problems, because I don't see how you can get around testing each combination of points (in the worst case). If rTarget is the radius of your special target circle, each pair of points with a distance less than their combined radii plus rTarget are a possible "seed pair" for the algorithm. Worst case, that goes for all of them. If you calculate an euclidean distance matrix of all points you may be able to rule out certain points or point combinations, but in general you will be looking at O(n!).
    – TToni
    Jul 10 '16 at 21:28
2

Here is a suggestion. I assume you want the maximum disk-area overlap, but this idea also works if you just want to maximize the number of circles partially covered.

Let r be the radius of the covering disk whose center you seek. Grow the radii of all the other disks by r. Call the resulting set of enlarged circles/disks C. Now compute the overlap depth of the arrangement determined by C. Place the center of your covering disk in a cell of the arrangement of maximum depth.

It is not easy to compute the cells of an arrangement of circles, but it can be done. You might approximate this by using a grid, essentially pixelating the disks.

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.