Subj : Re: Locating Nearest Neighbors in space (fast)
To   : comp.programming
From : Arthur J. O'Dwyer
Date : Thu Sep 08 2005 10:38 pm


On Thu, 8 Sep 2005, Googmeister wrote:
> Arthur J. O'Dwyer wrote:
>> On Thu, 8 Sep 2005, Googmeister wrote:
>>> Arthur J. O'Dwyer wrote:
>>>>    If you're only dealing with two dimensions, you can compute the Delaunay
>>>> triangulation of the set, and then /I think/ the nearest neighbor of any
>>>> point must be one of its neighbors in the triangulation.
[...]
>>> (e.g., if you insert all 2N points,
>>> its not true),
>>
>>    I don't understand what you mean there.
>
> There are two sets of points (array1 and array2), say N of each.
> If you take the Delaunay of all 2N, it might be the case that all
> points connected to V by a Delaunay edge are in the same array as V.
> In this case, I didn't understand what your algorithm would do since
> the OP wants the closest point in the other array. [I suspect now that
> my confusion was because you aren't actually considering the two
> set version.]

   Oops. Yes, I guess I wasn't reading with both eyes. :(  But in that 
case, the OP's problem is actually /closer/ to the problem conveniently
solved with Voronoi diagrams, as you said. Just find the point in A2
nearest to P, for each position P in A1, using the Voronoi diagram to 
guide you. Something like that.


   The problem I was trying to solve was: Given a set S of points, then 
for each point P, find P's nearest neighbor in S. That wasn't anything
like the OP's problem! :)


   Here's another interesting problem that's not the OP's: Given two sets
of points A1 and A2, find a matching between A1 and A2 that minimizes the 
sum of the distances between all pairs of matched points. Does the 
problem get significantly harder if we add the constraint that no matched 
pair can be separated by a distance greater than 'd'?

-Arthur

.