Voronoi Diagram

Given a collection of points V in a space S, define a map from S to V by saying that f(s) = v such that dist(s,v) is minimal. This defines a cell around each point of V, and points where the choice is non-unique are the boundaries. Such a division of S is a VoronoiDiagram.

More colloquially, from each point start growing a cell, each cell from each point growing at the same rate. In each direction, only stop growing once you touch another cell. Think "Expanded Polystyrene."

This is the same construction known to crystallographers for the Wigner-Seitz cells of a lattice.

We can now create a graph on V by setting e(u,v)=1 if there is some point s in S that chose between u and v only. This is then a DelaunayTriangulation.

KeithBraithwaite once toyed with the idea of using a Voronoi diagram constructed from the positions of wireless base-stations as a first approximation to a cell coverage prediction. Although it seems an obvious first step, his then employer didn't go for the idea.

Instead we used used the union of the triangles formed by the location of the site and the end-points of the maximal subsegments of the line segments forming the boundaries of the features in the topographical data that had line-of-sight to the site. For dense urban terrain (which is what we were primarily interested in) that gives a pretty accurate first approximation, although it involves quite a bit of intermediate calculation to find the line-of-sight subsegments

This tool has now been superseded.

TomAnderson toyed with the idea of using a VoronoiDiagram (or rather, a DelaunayTriangulation) to compute jump-lines for an SF starmap.

http://web.archive.org/web/20030327054552/http://users.ox.ac.uk/~univ0938/sc/

This is probably the same geometry implied by the AldersonDrive? in LarryNiven's Mote books.

CategoryMath