Laguerre Voronoi Diagram on the Sphere

K. Sugihara

Journal for geometry and graphics, Tome 6 (2002) no. 1, pp. 069-082.

Résumé

The Laguerre Voronoi diagram, also called the power diagram, is one of the important generalizations of the Voronoi diagram in the plane, in which the generating points are generalized to circles and the distance is generalized to the Laguerre distance. In this paper, an analogue of the Laguerre Voronoi diagram is introduced on the sphere. The Laguerre distance from a point to a circle on the sphere is defined as the geodesic length of the tangent line segment from the point to the circle. This distance defines a new variant of the Voronoi diagram on the sphere, and it inherits many characteristics from the Laguerre Voronoi diagram in the plane. In particular, a Voronoi edge in the new diagram is part of a great circle (i.e., the counterpart of a straight line), and the Voronoi edge is perpendicular to the great circle passing through the centers of the two generating circles. Furthermore, the construction of this diagram is reduced to the construction of a three-dimensional convex hull, and thus a worst-case optimal O(n\log n) algorithm is obtained. Applications of this diagram include the computation of the union of spherical circles and related problems.