Subj : Re: Locating Nearest Neighbors in space (fast)
To   : comp.programming
From : Googmeister
Date : Thu Sep 08 2005 04:36 pm


KRK wrote:
> I like the idea about partitioning the space into several cubes.  You could
> do that and move recursively to smaller and smaller cubes.  I think I will
> try that.  As far as triangulation goes, I know what that is and use it with
> matlab, but I don't have time to look into it and write code, test it,
> etc... to do the triangulation for my particular problem.

You might also try Bentley's multidimensional divide-and-conquer
trick, which resembles your recursive idea. It will guarantee something
like O(N log N) or O(N log^2 N) for your problem, but might be more
work than you want, and your problem might not demand such
a worst-case guarantee.

http://portal.acm.org/citation.cfm?id=358850

.