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.

  • $\begingroup$ 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. $\endgroup$ Sep 9, 2016 at 2:38
  • $\begingroup$ @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! $\endgroup$
    – Mdev
    Sep 9, 2016 at 2:40
  • $\begingroup$ 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. $\endgroup$
    – user856
    Sep 9, 2016 at 2:41

1 Answer 1


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.

Alternatively, and this personally seems a little overkill, you can do a thing where you repeatedly add new points and the circle around them, and use the circles to cut space into regions; the region that has the most points near it will win, and any point inside that region will give the largest number of points.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .