How to find map position with most POI inside a given radius

[ChrisClever]

Hello!
I'm having a problem with an assignment and I thought maybe some of you had already dealt with something similar.

I have a database of about 10,000 POIs with addresses, lat/lon and a specific value assigned to each point.

The task is to find a point on the map which has the POI with the highest total value within a radius of 500m.

So far, the closest I have come to a solution is taking the minimum and maximum values of lat/lon from the city limits and creating a table based on them containing combinations of all longitudes and latitudes every ~100m.
The resulting table has about 100,000 rows.
For each of these rows the distance to each POI is calculated and if it is <= 500m then the value is summed.

And it works. At least in theory.
Of course, the problem turned out to be system resources. Additionally, intervals every 100m are not ideal in terms of measurement accuracy.

There must be a more sensible way to solve this, but I can't think of it...

[AlexisOlson]

This is a difficult problem to solve efficiently. I've tried to read up on the literature but most of the papers on it are behind paywalls, so I'm not able to do much more than point you at this question on StackOverflow:

https://stackoverflow.com/questions/3229459/algorithm-to-cover-maximal-number-of-points-with-one-cir...

[johnt75 · Accepted solution]

Can you translate 500m into lat / long degress? If so, you could add & subtract them to your starting point giving you minimum and maximum values for lat / long. Filter your POIs to only those which fall inside the range, then do your distance calculations on those. Sum the values for any which fall inside 500m.

[ChrisClever]

Yeah!

As always - when looking for complex solutions the easiest ones are hard to find.

The 500m into lat/long translation is not as easy as it seems. But i figured out a rough estimate would do the job with drastically impoving the performance and it did!

Thanks!