Publications

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

Search for Publication


Year(s) from:  to 
Author:
Keywords (separated by spaces):

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}
}