Multi-dimensional Nearest Neighbor Algorthm: Got one
 

Can anyone send me an efficient VBA multi-dimensional (2-D or 3-D) for
finding the nearest neighbors to each point in a set of points?
Thanks.

Multi-dimensional Nearest Neighbor Algorthm: Got one
 

This is just a sample.

Let's say we have a set of points in rows 1 thru 100 where column A contains
the x-coordinate and column B contains the y-coordinate.

The first point [A1:B1] is the target point and we want to find which point
in 2 thru 100 that is nearest to this first point.

Enter and run:

Sub nearest_neighbor()
mn = ((Cells(1, 1).Value - Cells(2, 1).Value) ^ 2 + (Cells(1, 2).Value -
Cells(2, 2).Value) ^ 2) ^ 0.5
where = 1
For i = 3 To 100
w = ((Cells(1, 1).Value - Cells(i, 1).Value) ^ 2 + (Cells(1, 2).Value -
Cells(i, 2).Value) ^ 2) ^ 0.5
If w < mn Then
mn = w
where = i
End If
Next
MsgBox (where)
End Sub

It will output the row containing the point nearest to [A1:B1]
--
Gary's Student


"Jim" wrote:

Can anyone send me an efficient VBA multi-dimensional (2-D or 3-D) for
finding the nearest neighbors to each point in a set of points?
Thanks.

Multi-dimensional Nearest Neighbor Algorthm: Got one
 

Thanks, but that one I know.
I need the nearest neighbor to each point, for all points. The method
you used takes of order n^2 operations: 100 for each point and 100 to
search for the minimum distance to that point.
I thought that there were some algorithms that were linear in the
number of points (n^1).
Here's a reference to an N^1.5 algorithm:

http://cgm.cs.mcgill.ca/~soss/cs644/projects/perrier/

Thanks,
Jim