To Voronoi (and if so how)?

pileswasp has asked for the wisdom of the Perl Monks concerning the following question:

I've got a bit of a coordinates problem.
Given 2 sets of X,Y coordinates (say 161,000 and 2000) for each of the 2000 sets of coordinates I need to find the closest of the 161,000

Brute force would just be:

for (@shortlist) {
    for (@longlist) {
        # what's the distance
        # and is it shorter than the shortest so far
    }
}
[download]

but that's going to take ages! I've been doing a bit of research and there's an algorithm in the Oreilly Mastering Algorthms in Perl book, but a) it's broken for equal distances; b) it doesn't help me if there are two points in the big list which are closer together than the point I am checking is to anything else (if you see what I mean) and; c) my brain hurts from reading too many papers on algorithms for one wednesday afternoon.

I've also come across some mention of 'Voronoi and Delauney diagrams' which seem (if I'm still reading straight after the last couple of hours) like it would give me a 'compute-once-read-lots' set of data about the large set which would work fine for what I'm after if I stored it. Problem is I can't find a website that'll speak to me in anything other than mathematical symbols and notations.

My basic questions boil down to:

Am I on the right track?
- If not can anyone suggest a different approach?
- If so can anyone point me in the direction of a plain english maths site?
Any advice on doing this in perl at all (though if it's don't that would be awkward :)?

Many thanks in advance

Comment on To Voronoi (and if so how)? Download Code

Replies are listed 'Best First'.
Re: To Voronoi (and if so how)? by Albannach (Monsignor) on Aug 22, 2001 at 19:51 UTC
The Stony Brook Algorithm Repository is a great resource for problems like this, and they even have a discussion of your problem here that offers a few options and code (though not in Perl ;-(). -- I'd like to be able to assign to an luser	[reply]
Why bother with Voronoi? A walkabout could work... by dragonchild (Archbishop) on Aug 22, 2001 at 19:52 UTC
ponders You're doing everything by 1-dim lists. Why not do your coordinate lists as a single 2-dim list? It'll be memory-intensive, but should lend itself to some rather neat possibilities. For example, you could set the value of `$plane[$x][$y]` to 'S' for if it's shortlist-only, 'L' for longlist-only, and 'SL' if it's both. In the simple case of 'SL', you know the closest one. Otherwise, you would do a walk-about. Start by checking the four to the N, S, E, & W. Then, check the NE, NW, SE, & SW. And, then keep doing that, keeping in mind the very simple distance algorithm and how it's affected by number-over and number-up. You're doing sort of a radiating-out-from-the-center algorithm. ------ /me wants to be the brightest bulb in the chandelier! Vote paco for President!	[reply] [d/l]
Re: To Voronoi (and if so how)? by runrig (Abbot) on Aug 22, 2001 at 22:05 UTC
Reini Urban used to have a module for that (Voronoi and Delauney diagrams, and geometry in general), now all I see is a README file (Geometry-0.02.readme, that is). I remember that at least the Delauney triangulation part was tied to someone else's C code. You might ask him what happened to his module or track down the C code yourself. Update: Found it off of his hompage here.	[reply]