Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

So lets say we have a set of gps data points and your current location. If asked to give the closest point to your current location we can utilize a heap with the distance being the key. Now if we update the current location, I suspect that only a few of the keys will change enough to violate the heap property. Would it be more efficient to rebuild the heap after recalculating the keys or to run heapify (assuming that only a few of the keys have changed enough). It is assumed that we don't jump around with the new location (new current location is close to the last current location).

share|improve this question
    
Your question is probably answered in GIS StackExchange. –  RichardM Nov 16 '11 at 15:08

1 Answer 1

up vote 1 down vote accepted

I'm pretty sure you can't (mis-)use heaps for your purpose. I suggest you use data structures that are specifically built for your problem instead.

If your set of GPS data points hardly ever changes, KD-trees are probably the best choice for this. If your data points are also moving around, then quad-trees are probably the best. If you're feeling particularly algorithmic, you could even try to employ locality-sensitive hashing.

If you don't want to query your data structure every time your current location changes, you could instead find the two closest points, compute the difference in the distances from you to the two points, and only re-query the data structure if your current location has moved away from its position when you queried the data structure than this difference.

So, if A and B are the two nearest points (A being the nearest) to the current position D, and you then start moving from D again and end up at position C, then you only have to query the structure again if |B-D| - |A-D| <= |C-D|, because only then have you moved away far enough from D to have a different point E become (potentially) interesting.

If your data points and current location can be really far away from each other, you may have to take the rounding of the earth into account. You probably don't have to, but don't forget about it.

share|improve this answer
    
The curvature of the earth must be considered unless you can make the assumption that distances between locations is always very small. This is also addressed in the answer to question referenced above (the great circle distance is a suitable approximation). –  RichardM Nov 16 '11 at 15:08
    
It is possible to use heaps (not sure if you were saying you didn't think it was or not) but I think the KD-Tree is a better option. Thanks –  Trevor Adams Nov 16 '11 at 15:39
    
@TrevorAdams, surely if you actually make any queries you have to pull the values out of the heap, and then the question doesn't make sense because rebuilding the heap is the only choice. –  Peter Taylor Nov 16 '11 at 15:49
    
Well if I was just going to get the closest point, act on it and then get the next closest point at a future time I could store the distances. I could then grab the minimum distance, pull that out and act on it. We can then either keep it removed or replace it with a new distance (since we have a new location) –  Trevor Adams Nov 16 '11 at 16:41
    
The problem with heaps is this: your heap will have to store the distances to your current point. If your current point changes, all the distances in the heap are now wrong, which means you have to completely recreate your heap to contain the distances to the new point. –  Alex ten Brink Nov 16 '11 at 23:32

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.