Subj : Re: Locating Nearest Neighbors in space (fast)
To   : comp.programming
From : Christer Ericson
Date : Sat Sep 10 2005 06:38 am

In article <dfps46$585$1@grapevine.wam.umd.edu>, karlk@eng.umd.edu 
says...
> Does anyone know a fast algorithm to do this, preferably one that doesn't 
> require fancy knowledge of data structures etc since I'm not a professional 
> programmer.  Thanks.

The canonical data structure for nearest neighbor queries (in low
dimensions, at least) is the k-d tree.  Given a k-d tree of your
query points, you can implement an efficient nearest neighbor
query in about 10 lines of code.  K-d trees are a sufficiently fast
and simple solution that I would not waste my time on other solutions.

-- 
Christer Ericson
http://realtimecollisiondetection.net/

.