1

I have multiple points on a map each with their own latitude and longitude.
Each point has a value associated to it.
Given a radius $r$, I want to find the centre of the circle with radius r that encompasses the largest aggregation of point values possible.

I need to make this scalable so it would need to work for hundreds of thousands of points.

Any ideas on how to get started on this would be greatly appreciated.

enter image description here

InanimateBeing
  • 3,074
MountainMJ
  • 11
  • Random thought - could you treat each point as having the same mass and then find the centre of mass of all the points - I wonder if that would be where the centre of the circle should be? – Mufasa Aug 26 '22 at 08:41
  • Another random thought - start with a square of side length $r$ instead of a circle as maybe finding where such a square should lie would be a much easier problem to solve. Then maybe the circle should lie somewhere within that square? – Mufasa Aug 26 '22 at 08:46
  • In my last comment I meant to say "Then maybe the centre of the circle should lie somewhere within that square?" – Mufasa Aug 26 '22 at 08:52
  • I thought about finding the centre of mass and I think that is a good starting point. Why would you treat them all equally though? I think you would want them to be treated normally so the centre would be weighted towards the higher values? – MountainMJ Aug 26 '22 at 09:30
  • I would consider each point as having the same mass and then find the centre of mass. After more thought on this I do not think it will give the correct answer. Consider the case where all points lie on the circumference of a circle with a radius larger than $r$. The centre of mass will be at the centre of that circle and all the points will be excluded. Maybe solving the square with side length $r$ might be more fruitful? – Mufasa Aug 26 '22 at 09:44

0 Answers0