Given a list of the 2D coordinates of all the Pokestops in my city, how do I find a circle with radius 'r' with the most Pokestops in it?

Given a list of coordinates and a circle of radius 'r', how would I go about finding the center of the circle C in which the most points lie?

My brute force solution: I have a list of coordinates (Pokestops) that I will iterate through. For each coordinate X in the list, there will be a circle C with center X. There will be ~10 other circles C1-10 centered around a point on the circumference of circle C, where each of those points are coordinates evenly separated throughout the circumference of C. I will check how many other Pokestops are within those 10 circles individually and track the circle with the highest total number of Pokestops.

However, I realize that the most optimal circle might not be one where a Pokestop lies on the circumference of the circle. The most optimal circle would actually likely be one in which no Pokestops touch the outer edge of the circle.

How do I account for this? My brute force solution will only track circles with Pokestops on the outer edge.

For what it's worth, I'm asking because I have a list of all Pokestops in my city and want to iterate through all of them to find the best/most optimal areas I can sit in that will have the highest number of stops.

• Actually, having a hotspot on the outer edge is a good restriction: you know that if you move the circle away from that point your hotspot count goes down one. Actually actually, I think you can do two hotspots on the edge of the circle. This reduces the number of locations you have to check by quite a lot. Sep 9, 2016 at 2:38
• @DanUznanski I think you're right. I originally thought that and then got confused when I 'realized' I could find a more optimal circle where the points are closer to the center, but I don't think that actually matters. Figured someone on here would know better than me!
– Mdev
Sep 9, 2016 at 2:40
• A disk of radius $r$ centered at $C$ contains a hotspot $P$ iff the disk of radius $r$ centered at $P$ contains $C$. So you can imagine drawing a disk around each hotspot and looking for a point $P$ contained in as many such disks as possible. I don't know if this leads to a better algorithm, but I find it an easier way to visualize the problem.
– user856
Sep 9, 2016 at 2:41

Given any pair of points less than $2r$ apart, there are two circles of radius $r$ that pass through those two points. For each such circle you can count how many points are within them.