Please use this identifier to cite or link to this item:
Title: The voronoi diagram of curved objects
Authors: Alt, H.
Cheong, O.
Vigneron, A. 
Issue Date: 2005
Citation: Alt, H., Cheong, O., Vigneron, A. (2005). The voronoi diagram of curved objects. Discrete and Computational Geometry 34 (3) : 439-453. ScholarBank@NUS Repository.
Abstract: Voronoi diagrams of curved objects can show certain phenomena that are often considered artifacts: The Voronoi diagram is not connected; there are pairs of objects whose bisector is a closed curve or even a two-dimensional object; there are Voronoi edges between different parts of the same site (so-called self-Voronoi-edges); these self-Voronoi-edges may end at seemingly arbitrary points not on a site, and, in the case of a circular site, even degenerate to a single isolated point. We give a systematic study of these phenomena, characterizing their differential-geometric and topological properties. We show how a given set of curves can be refined such that the resulting curves define a "well-behaved" Voronoi diagram. We also give a randomized incremental algorithm to compute this diagram. The expected running time of this algorithm is O(n log n). © 2005 Springer Science+Business Media, Inc.
Source Title: Discrete and Computational Geometry
ISSN: 01795376
DOI: 10.1007/s00454-005-1192-0
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Feb 13, 2019


checked on Feb 13, 2019

Page view(s)

checked on Jan 27, 2019

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.