Publications

Voronoi Tessellation of Points with Integer Coordinates: Time-Efficient Implementation and Online Edge-List Generation

L. Ogniewicz and O. Kübler
Pattern Recognition
Vol. 28, No. 12, pp. 1839-1844, 1995

Abstract

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.

Download in postscript format

@Article{eth_biwi_00050,
  author = {L. Ogniewicz and O. K\"ubler},
  title = {Voronoi Tessellation of Points with Integer Coordinates: Time-Efficient Implementation and Online Edge-List Generation},
  journal = {Pattern Recognition},
  year = {1995},
  month = {},
  pages = {1839-1844},
  volume = {28},
  number = {12},
  keywords = {tessellation, Computational Geometry, Delaunay triangulation, Voronoi diagram}
}