# Place circle such that it overlaps the most possible other circles

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?
• 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!)`. Jul 10, 2016 at 21:28