The Voronoi diagram of curved objects

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).
Publisher
SPRINGER
Issue Date
2005-09
Language
ENG
Keywords

MEDIAL AXIS ALGORITHM; PLANAR DOMAINS; COMPUTATIONAL GEOMETRY; BOUNDARIES

Citation

DISCRETE & COMPUTATIONAL GEOMETRY, v.34, no.3, pp.439 - 453

ISSN
0179-5376
DOI
10.1007/s00454-005-1192-0
URI
http://hdl.handle.net/10203/298
Appears in Collection
CS-Journal Papers(저널논문)
Files in This Item
000231312500005.pdf(242.22 kB)Download
  • Hit : 484
  • Download : 278
  • Cited 0 times in thomson ci
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡClick to seewebofscience_button
⊙ Cited 16 items in WoSClick to see citing articles inrecords_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0