Journal
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS
Volume 23, Issue 2, Pages 183-194Publisher
ELSEVIER
DOI: 10.1016/S0925-7721(02)00077-9
Keywords
computational geometry; Voronoi diagram; sphere; inversion; stereographic projection; furthest-site Voronoi diagram
Categories
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available