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?
- 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?