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

---

---

Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!

Titles consisting of a single word are discouraged, and in most cases are disallowed outright.

Read Where should I post X? if you're not absolutely sure you're posting in the right place.

Please read these before you post! —

• How do I compose an effective node title?
• How do I post a question effectively?
• Markup in the Monastery

Posts may use any of the Perl Monks Approved HTML tags:

a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr

You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)

	For:		Use:
	&		&
	<		&lt;
	>		&gt;
	[		&#91;
	]		&#93;

Link using PerlMonks shortcuts! What shortcuts can I use for linking?

See Writeup Formatting Tips and other pages linked from there for more info.