A list-processing approach to compute Voronoi diagrams and the Euclidean distance transform

Abstract

We propose an efficient Voronoi transform algorithm for constructing Voronoi diagrams using segment lists of rows. A significant feature of the algorithm is that it takes segments rather than pixels as the basic units to represent and propagate the nearest neighbor information. The segment lists are dynamically updated as they are scanned. A distance map can then be easily computed from the segment list representation of the Voronoi diagram. Experimental results have demonstrated its high efficiency. Extension of the algorithm to higher dimensions is also discussed.