Voronoi diagrams on the sphere

Given a set of compact sites on a sphere, we show that their spherical Voronoi diagram can be computed by computing two planar Voronoi diagrams of suitably transformed sites in the plane. We also show that a planar furthest-site Voronoi diagram can always be obtained as a portion of a nearest-site Voronoi diagram of a set of transformed sites. Two immediate applications are an O(n log n) algorithm for the spherical Voronoi diagram of a set of circular arcs on the sphere, and an O(n log n) algorithm for the furthest-site Voronoi diagram for a set of circular arcs in the plane. (C) 2002 Elsevier Science B.V. All rights reserved.
Publisher
ELSEVIER SCIENCE BV
Issue Date
2002-09
Language
ENG
Keywords

MEDIAL AXIS TRANSFORM; CONSTRUCTION; ALGORITHM

Citation

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, v.23, no.2, pp.183 - 194

ISSN
0925-7721
DOI
10.1016/S0925-7721(02)00077-9
URI
http://hdl.handle.net/10203/311
Appears in Collection
CS-Journal Papers(저널논문)
Files in This Item
2001-47.pdf(230.37 kB)Download
  • Hit : 603
  • Download : 251
  • Cited 0 times in thomson ci
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡClick to seewebofscience_button
⊙ Cited 22 items in WoSClick to see citing articles inrecords_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0