I'm in need of an algorithm to find the best spot for a circle with a fixed radius r to cover as many points as possible on a 2D grid, preferably O(n).
Currently I tried 2 different approaches:
- The averaging Method
- The 'Heat-Map' Method
On the averaging Method I calc the center of all points and then I check how many points are in range (r) of that center, if the number is as high as the given points it returns the spot, else the furthest point is removed from the list and the steps repeat.
+: Very fast -: Often inaccurate
On the Heat-Map method I generate possible circle center points around all points. If a point is already created I increase it's count by 1. The point with the highest count and lowest total distance to the points in range (r) is the center.
+: Perfect center (depending on scale) -: Slow (depending on scale)
About scale: map is huge 10000x10000, a circle with radius 400 would contain thousands of possible centers, so I scale all points to the same system with roundings. The higher the scale, the less points and faster algorithm but more inaccurate center. But still more accurate than 1. Method.
Do you guys know any other algorithms/ways/Tipps/Performance Boosters?
Edit: maybe minimum enclosing circle + removing furthest Point Till MEC.radius <= Radius...
Edit2: or connect all points with lines and check for most intersections, just came to my mind
Edit: Here's an image with Algorithm #2
Another Image of Algorithm #2
