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 |
Source: | 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
29
checked on Mar 19, 2018
WEB OF SCIENCETM
Citations
17
checked on Mar 19, 2018
Page view(s)
54
checked on Apr 21, 2018
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.