0

I have two lists listA and listB containing tuples of latitude/longitudes. Using Python, for each element of listA, I want to get the closest lat/lon from listB. I can use the haversine formula, but the complexity of the algorithm is O(n*m), where n is len(listA) and m len(listB). I was wondering if there is a better, more efficient way of doing this kind of computation, maybe using some indexes or some sort of pre-processing?

Stephane Maarek
  • 5,202
  • 9
  • 46
  • 87
  • 5
    Related (or possibly a dupe): http://stackoverflow.com/q/6656475/189134 – Andy Oct 05 '15 at 13:42
  • I think you can have an aproximation of the distance calculating the euclidean distance – David Lemon Oct 05 '15 at 13:42
  • 2
    @DavidLemon, yeah, but it depends on the use case. If all the coordinates are close together - say, in a single city - then it's a good approximation. But things get thorny if the actual shortest path between points goes over the international date line or one of Earth's poles. – Kevin Oct 05 '15 at 13:48
  • 1
    I don't think this is really python related, more to do with algorithms. Maybe try [programmers.se] on stackexchange.com, [according to this](http://meta.stackexchange.com/questions/165519/where-should-i-post-questions-about-algorithms-stack-overflow-or-programmers-se). – Peter Wood Oct 05 '15 at 13:55
  • @PeterWood agreed, though I guess I'm not sure why this is being downvoted/suggested to be closed here? Either way, I would be more than happy to see it come to Programmers. – Jimmy Hoffa Oct 05 '15 at 14:04
  • @JimmyHoffa well, if it is [tag:python] related it's too broad, or is looking for a library (the only answer suggests a library), or closed as a duplicate (the only answer also points to another SO question), but it probably should be in [tag:algorithms] or [programmers.se]. – Peter Wood Oct 05 '15 at 14:13
  • 1
    If this came to programmers, it would probably be closed as a duplicate of [Finding the closest n points to any arbitrary point in two dimensions (r-tree, quadtree, spatial index)](http://programmers.stackexchange.com/q/279038/88986) – durron597 Oct 05 '15 at 14:20
  • hey all, thanks for your help. I've never heard of programmers before so this is definitely the place to be for this question. I validated the answer just because it does help me in some ways. My whole question was around the complexity of O(nm) and ways to improve that. Definitely algorithm oriented – Stephane Maarek Oct 05 '15 at 14:26
  • 3
    @Stephane Please read the question I've linked in my previous comment and see if it answers your question before asking on Programmers. If not, please be sure to include in your question why that question doesn't answer yours. Also, you should have a look at [R tree implementation in Python](https://pypi.python.org/pypi/Rtree/) – durron597 Oct 05 '15 at 14:27
  • R-tree definitely helps and I think they answer my question. Definitely helps the complexity by introducing a log. Perfect! – Stephane Maarek Oct 05 '15 at 14:31

0 Answers0