Hi All,

   I'm devising a program to find the nearest neighbor for each point
in a given set of size N. A common solution of this problem is to
compare the distances between a given point and all the other points
pair by pair. Then, for a single point, there are N-1 comparisons. So,
the total number of comparisons should be (N-1)xN.

  To speed up the program, is it better to use a sorting algorithm
instead of pairwise comparisons?
I mean to store the distances of a given point in a temporary array,
sort it with an appropriate sorting algorithm and then choose the
first element as the shortest distance.

  Thanks!

Regards,
Nathan

On Nov 4, 9:11 pm, nathanw...@gmail.com wrote:
>    I'm devising a program to find the nearest neighbor for each point
> in a given set of size N. A common solution of this problem is to
> compare the distances between a given point and all the other points
> pair by pair. Then, for a single point, there are N-1 comparisons. So,
> the total number of comparisons should be (N-1)xN.
>
>   To speed up the program, is it better to use a sorting algorithm
> instead of pairwise comparisons?
> I mean to store the distances of a given point in a temporary array,
> sort it with an appropriate sorting algorithm and then choose the
> first element as the shortest distance.

Sorting is a terrible idea.  You'd be doing either n sorts of O(n log
n) time or one sort of O(n^2) size data, which again is O(n^2 log n)
--- slower than the simple each city against all others and wasteful
of memory, too.  It's the same reason you don't sort a list of
integers just to find their min!

A common approach to solving this problem efficiently is to build a kd-
tree, which takes average case O(n log n) time.  You can also look up
all the nearest neigbors in O(n log n) time.  This is much better than
your proposals.

There are more complex variations on the kd-tree idea that guarentee
O(n log n) to build and O(log n) to look up rather than provide it as
an average case.  Try comp.graphics.algorithms .

Still, unless n is certain to be truly huge, you ought to give the
brute force computation a try.  If it's fast enough and n will never
increase, you're done.

nathanwh71@gmail.com schrieb:
> Hi All,
> 
>    I'm devising a program to find the nearest neighbor for each point
> in a given set of size N. A common solution of this problem is to
> compare the distances between a given point and all the other points
> pair by pair. Then, for a single point, there are N-1 comparisons. So,
> the total number of comparisons should be (N-1)xN.

Are you in 2D? Then use the Delaunay triangulation. Look for steve
fortunes code or qhull

	Christian