let's say I have a set of geographic locations (lat, lng) resulting from a query. Those locations have some kind of internal ranking, my set is sorted by this number in a descending order.

Now I'm trying to interpolate this data by eliminating all locations in a certain distance from each other. For example, starting with the highest ranking, point A must not have any adjacent points closer than 300 meters, so point B must be in distance of at least 300 meters away.

First thing came to mind was creating some kind of chess table which contains all distances and odd the low ones out. This may work for 5, 10, maybe 100 points but obviously won't scale well. I expect an average of 10000 points to be processed regularly. So I would have to query and post-process 9999 times for each point existing (I know this could be optimized minimally but you get the idea).

Second idea is processing the data like a tree, starting with the highest ranking point(s) and working my way down. Like creating an incremental search 'map', each 'allowed' point adding a circle of 300m radius as 'disallowed' area used as template for the next tier. I have used the haversine formula before and understand how to achieve this but I'm not sure performance-wise and fear eliminating too many points from my set.

So my question is, how to approach this with a goal of minimizing cost? Is there maybe an algorithm targeting this problem I don't know about yet? Help appreciated.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.