A fast algorithm for Voronoi diagram calculation based on distance doubling

An efficient algorithm is described for calculation of the Voronoi diagram over one- and two-dimensional lattices. The algorithm proceeds by propagating the location of Voronoi points through the lattice using a distance-doubling strategy. This algorithm is designed for implementation on a fine-grain parallel computer such as the Connection Machine. It is shown how the algorithm is extended to calculation of distance-from-region computation and the use of nonstandard metrics. Two algorithms are presented for the calculation of the Voronoi diagrams over one- and two-dimensional lattices. Both algorithms propagate the explicit location of the nearest Voronoi point rather than the distance to the point and so are more accurate than traditional methods. The first algorithm is based on brushfire propagation while the second algorithm relies on distance doubling. It is found that distance-doubling algorithm is more efficient than the classical algorithm when at least one Voronoi polygon is large. It is found that there is little penalty in using the updated brushfire algorithm over the traditional algorithm