This is quite closely related to boids: http://www.red3d.com/cwr/ Simply put, each boid is aware of its near neighbours: not just the nearest one, but all that are nearer than some chosen distance. For that, the space is divided into partitions that keep track of the boids that are are within it, and also each boid knows in which partition it is. The data structure must be easily maintained as the boids move. If the density of boids should be more or less even, a simple one level uniform partitioning works well. On the other hand, if there should be clusters of boids and also vast empty spaces, one can use some kind of a quad-, oct- etc. tree (2D/3D) to recursively subdivide the space, with density tresholds to trigger how the leaf compartments split or are joined together.
On Nov 17, 10:51 pm, Paksas <ptroc...@gmail.com> wrote: > 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=.
