At it simplest, you could use a spatial partitioning structure of some sort - I'm guessing a quadtree would be more than perfect in this case. It would cut down your search time to O(lg(n)).
The problem becomes a bit more complicated if you assume the people can move (well - that's obvious, but maybe your problem doesn't require that kind of detail). In that case I'd still go for with a quadtree, only this time have entites representing people update their position in the quadtree. Each tree sector could contain pointers to its neighbors, so a position update would involve searching through the four neighbouring sectors - done in O(1). Of course this imposes an additional requirement on the tree - it has to have even depth of all its branches - but that's not that big a deal. You can simply limit the tree depth at some point and still get good query time results. Of course there are other more sophisticated structures out there - this is just the simplest ... :) Cheers, Paksas On 17 Lis, 15:09, Tiago Reul <tiagor...@gmail.com> wrote: > Suppose that you have the position of each person in the world. > Position is the pair (latitude, longitude). > > How to represent the data so that I can find the nearest person > from a point (φ,λ) without comparing to every pair in the collection? -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=.
