#1
|
|||
|
|||
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 |
#2
|
|||
|
|||
algorithm help
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. -- ___ _______ ___ ___ ___ __ ____ / _ \/ __/ _ | / _ \ / _ \/ _ |/ / / / / / // / _// __ |/ // / / ___/ __ / /_/ / /__ /____/___/_/ |_/____/ /_/ /_/ |_\____/____/ |
#3
|
|||
|
|||
algorithm help
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. |
#4
|
|||
|
|||
algorithm help
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. ___ _______ ___ ___ ___ __ ____ / _ \/ __/ _ | / _ \ / _ \/ _ |/ / / / / / // / _// __ |/ // / / ___/ __ / /_/ / /__ /____/___/_/ |_/____/ /_/ /_/ |_\____/____/ |
#5
|
|||
|
|||
algorithm help
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/ |
Thread Tools | |
Display Modes | |
|
|
Similar Threads | ||||
Thread | Thread Starter | Forum | Replies | Last Post |
The best multi-object algorithm | [email protected] | Misc | 6 | June 4th 05 10:59 PM |
Life on Other Plants, An Algorithm? | Benign Vanilla | Misc | 22 | August 14th 04 09:49 AM |
Bayer to RGB bicubic algorithm | Christian | CCD Imaging | 0 | January 29th 04 04:20 PM |
Algorithm for sunrise and sunset? | M?ht?n | Amateur Astronomy | 12 | December 24th 03 11:14 AM |
need lunar phase algorithm | Marty | Misc | 1 | August 11th 03 03:58 PM |