On Sat, 3 Nov 2007, Tim Woodall wrote:

On Mon, 29 Oct 2007 11:04:56 +0000,
Clive D. W. Feather wrote:
In article , Tom
Anderson writes
I'm trying to figure out how to program a computer to find these
automatically.

The approach I've taken in the past is very simple. Start with a grid
representing the entire area (to make it easy, say 1000 x 1000 with one
unit on the grid being 100 metres). Set up a list of locations of all
the stations. Then:
for each grid cell
best := infinity
for each station on the list
d := (distance from station to cell) squared
if d best then best := d
cell value := sqrt (best)

You can optimize things slightly by using a lookup table for the square
roots rather than calculating them each time.

Possibly. This is not as sure-fire a trick as it once was - you're saving
arithmetic operations, but giving your data cache a rough ride.

I'd have thought a more useful optimization would be:
If D(x,y) = x^2 + y^2

then D(x+1, y) = D(x, y) + 2x + 1
D(x, y+1) = D(x, y) + 2y + 1
D(x-1, y) = D(x, y) - 2x + 1
D(x, y-1) = D(x, y) - 2y + 1

This would only work if you inverted the loops, though, so you iterated
over stations on the outside, and grid cells on the inside. If you did
that, though, yes, this would be what we call 'strength reduction', a
venerable optimisation trick. Very well spotted that it can be applied
here!

A better optimisation, though, would be to start off by putting the
stations in a quadtree or some other spatial data structure (something
clever involving the Voronoi diagram?), so that you can find the nearest
station (or at least a small number of candidates) to each grid cell with
a fast lookup, rather than having to grind through every station in the
list.

Or at least, this would be true if there were a million stations. If there
are only a few hundred, brute force might still be quicker. Most
unsatisfying.

tom

--
Science which is distinguishable from magic is insufficiently advanced