1
$\begingroup$

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.

$\endgroup$
3
  • $\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

0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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