Voronoi diagrams on the sphere

Abstract

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(nlog n) algorithm for the spherical Voronoi diagram of a set of circular arcs on the sphere, and an O(nlog n) algorithm for the furthest-site Voronoi diagram for a set of circular arcs in the plane.