Voronoi tessellation of points with integer coordinates: Time-efficient implementation and online edge-list generation

摘要

The Voronoi tessellation in the plane can be computed in a particularly time-efficient manner for generators with integer coordinates, such as typically acquired from a raster image. The Voronoi tessellation is constructed line by line during a single scan of the input image, simultaneously generating an edge-list data structure (DCEL) suitable for postprocessing by graph traversal algorithms. In contrast to the generic case, it can be shown that the topology of the grid permits the algorithm to run faster on complex scenes. Consequently, in Computer Vision applications, the computation of the Voronoi tessellation represents an attractive alternative to raster-based techniques in terms of both computational complexity and quality of data structures.