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.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.