Monthly Archives: June 2011

I just thought this up last night: (math/CS warning)

Let’s say you have a large collection of points in a plane, and you need to find the closest point to point P. The obvious (and inefficient) way is to calculate the distance to every point, which requires N square roots and takes far too long to be useful in some cases (such as an early draft of Voronoid that didn’t work out because of this inefficiency). Here’s a better way I came up with:

• For every point Q, calculate |x_Q-x_P| and |y_Q-y_P|. Find the sum and maximum of these values and store them.
• Find the two points with the smallest sum and the smallest maximum.
• If the same point has the smallest value for both, you win! That’s the closest point to P. Otherwise…
• Go through the points again, using the stored values this time. For every point that has a smaller sum than that of the point with the smallest maximum and a smaller maximum than that of the point with the smallest sum, calculate the standard Euclidean distance from P: sqrt((x_Q-x_P)²+(y_Q-y_P)²). The closest point to P within this (likely very small) set of points is also the closest point overall.

I’m sure there are absurdly efficient algorithms for doing this better, but this one is very easy to implement (assuming it works, which I’ve sort of heuristically proven). In fact, I might go back and try my early version of Voronoid with this algorithm and see how it runs.