期刊
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS
卷 23, 期 2, 页码 183-194出版社
ELSEVIER
DOI: 10.1016/S0925-7721(02)00077-9
关键词
computational geometry; Voronoi diagram; sphere; inversion; stereographic projection; furthest-site Voronoi diagram
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据