Please use this identifier to cite or link to this item: https://doi.org/10.1007/s00454-005-1192-0
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. https://doi.org/10.1007/s00454-005-1192-0
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
URI: http://scholarbank.nus.edu.sg/handle/10635/38995
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.

SCOPUSTM   
Citations

31
checked on Nov 14, 2018

WEB OF SCIENCETM
Citations

20
checked on Nov 6, 2018

Page view(s)

60
checked on Oct 20, 2018

Google ScholarTM

Check

Altmetric


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