algorithm help

I have two problems that I need to solve, and before trying to perhaps
reinvent a wheel I'd thought I'd ask if anyone has a good pointer to
a solution.

Given a list of objects that are specified by two variables (either
X,Y or RA,DEC) and a function given the 'distance' between two
objects, does anyone have an efficient algorithm for calculating what
the distance for the nearest neighbor for each object is? I'll be able
to assume the list is sorted in one direction, and I'd like to avoid
the brute force n^2 method since the number of objects can get rather
large.

My second problem is given a two lists of objects, once again specifed
by two variables and a distance function, does anyone have an
efficient method for calculating what the nearest object in list B is
for each element of list A?

If anyone can give me a pointer to C or Fortran code that can solve
these problems I'd be grateful.

Greg

On Thu, 15 Jun 2006 01:05:00 +0000, Greg Hennessy wrote:

I have two problems that I need to solve, and before trying to perhaps
reinvent a wheel I'd thought I'd ask if anyone has a good pointer to a
solution.

Given a list of objects that are specified by two variables (either X,Y or
RA,DEC) and a function given the 'distance' between two objects, does
anyone have an efficient algorithm for calculating what the distance for
the nearest neighbor for each object is? I'll be able to assume the list
is sorted in one direction, and I'd like to avoid the brute force n^2
method since the number of objects can get rather large.

My second problem is given a two lists of objects, once again specifed by
two variables and a distance function, does anyone have an efficient
method for calculating what the nearest object in list B is for each
element of list A?

If anyone can give me a pointer to C or Fortran code that can solve these
problems I'd be grateful.

Greg

The "bubble sort" algorithm is pretty good.


--

___ _______ ___ ___ ___ __ ____
/ _ \/ __/ _ | / _ \ / _ \/ _ |/ / / / /
/ // / _// __ |/ // / / ___/ __ / /_/ / /__
/____/___/_/ |_/____/ /_/ /_/ |_\____/____/

Dead Paul wrote:
On Thu, 15 Jun 2006 01:05:00 +0000, Greg Hennessy wrote:

I have two problems that I need to solve, and before trying to perhaps
reinvent a wheel I'd thought I'd ask if anyone has a good pointer to a
solution.

Given a list of objects that are specified by two variables (either X,Y or
RA,DEC) and a function given the 'distance' between two objects, does
anyone have an efficient algorithm for calculating what the distance for
the nearest neighbor for each object is? I'll be able to assume the list
is sorted in one direction, and I'd like to avoid the brute force n^2
method since the number of objects can get rather large.

My second problem is given a two lists of objects, once again specifed by
two variables and a distance function, does anyone have an efficient
method for calculating what the nearest object in list B is for each
element of list A?

If anyone can give me a pointer to C or Fortran code that can solve these
problems I'd be grateful.

Greg

The "bubble sort" algorithm is pretty good.


--

___ _______ ___ ___ ___ __ ____
/ _ \/ __/ _ | / _ \ / _ \/ _ |/ / / / /
/ // / _// __ |/ // / / ___/ __ / /_/ / /__
/____/___/_/ |_/____/ /_/ /_/ |_\____/____/

Bubble sort is n^2. You want tournament sort. The Tournament sort is
NLog(2)N in terms of its operations. What you have to do is sort for a
simple approximation of distance. Let us say we sort in x and then y.
We takev an object and take the nearest objects in x and y. We
initially minimize on x+y say and calculate distances. We stop when we
know it is impossible to find closer points.

On Thu, 15 Jun 2006 03:38:54 -0700, ianparker2 wrote:


Dead Paul wrote:
On Thu, 15 Jun 2006 01:05:00 +0000, Greg Hennessy wrote:

I have two problems that I need to solve, and before trying to perhaps
reinvent a wheel I'd thought I'd ask if anyone has a good pointer to a
solution.

Given a list of objects that are specified by two variables (either
X,Y or RA,DEC) and a function given the 'distance' between two
objects, does anyone have an efficient algorithm for calculating what
the distance for the nearest neighbor for each object is? I'll be able
to assume the list is sorted in one direction, and I'd like to avoid
the brute force n^2 method since the number of objects can get rather
large.

My second problem is given a two lists of objects, once again specifed
by two variables and a distance function, does anyone have an
efficient method for calculating what the nearest object in list B is
for each element of list A?

If anyone can give me a pointer to C or Fortran code that can solve
these problems I'd be grateful.

Greg

The "bubble sort" algorithm is pretty good.


--

___ _______ ___ ___ ___ __ ____
/ _ \/ __/ _ | / _ \ / _ \/ _ |/ / / / /
/ // / _// __ |/ // / / ___/ __ / /_/ / /__
/____/___/_/ |_/____/ /_/ /_/ |_\____/____/

Bubble sort is n^2. You want tournament sort. The Tournament sort is
NLog(2)N in terms of its operations. What you have to do is sort for a
simple approximation of distance. Let us say we sort in x and then y. We
takev an object and take the nearest objects in x and y. We initially
minimize on x+y say and calculate distances. We stop when we know it is
impossible to find closer points.

yep, i just revisited the bubble sort, it's n^2 :-(

--
The truth is, that it is quite an error to suppose that absence of
definite convictions gives the mind freedom and agility. A man who
believes something is ready and witty, because he has all his weapons
about him. He can apply his test in an instant. The man engaged in
conflict with a man like Mr. Bernard Shaw may fancy he has ten faces;
similarly a man engaged against a brilliant duellist may fancy that
the sword of his foe has turned to ten swords in his hand. But this is
not really because the man is playing with ten swords, it is because
he is aiming very straight with one. Moreover, a man with a definite
belief always appears bizarre, because he does not change with the
world; he has climbed into a fixed star, and the earth whizzes below
him like a zoetrope. Millions of mild black-coated men call themselves
sane and sensible merely because they always catch the fashionable
insanity, because they are hurried into madness after madness by the
maelstrom of the world.

Heretics IV, Mr Bernard Shaw, Chapter 4 By Gilbert K Chesterton.

___ _______ ___ ___ ___ __ ____
/ _ \/ __/ _ | / _ \ / _ \/ _ |/ / / / /
/ // / _// __ |/ // / / ___/ __ / /_/ / /__
/____/___/_/ |_/____/ /_/ /_/ |_\____/____/

On 2006-06-15, Dead Paul wrote:
On Thu, 15 Jun 2006 03:38:54 -0700, ianparker2 wrote:


Dead Paul wrote:
On Thu, 15 Jun 2006 01:05:00 +0000, Greg Hennessy wrote:

I have two problems that I need to solve, and before trying to perhaps
reinvent a wheel I'd thought I'd ask if anyone has a good pointer to a
solution.

Given a list of objects that are specified by two variables (either
X,Y or RA,DEC) and a function given the 'distance' between two
objects, does anyone have an efficient algorithm for calculating what
the distance for the nearest neighbor for each object is? I'll be able
to assume the list is sorted in one direction, and I'd like to avoid
the brute force n^2 method since the number of objects can get rather
large.

I think you'd want to use Delaunay triangulation/Voronoi decomposition,
which directly gives the nearest neighbors to each point.
There are N-log-N algorithms and freely available code to do this
(for Euclidean metrics and for the sphere). See e.g.
http://www.qhull.org/