A list-processing approach to compute Voronoi diagrams and the Euclidean distance transform
Weiguang Guan, Songde Ma · IEEE Transactions on Pattern Analysis and Machine Intelligence · 1998
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.