Laguerre Voronoi Diagram on the Sphere
Kōkichi Sugihara · 2002
TheLaguerreVoronoidiagram,alsocalledthepowerdiagram,isone oftheimportantgeneralizationsoftheVoronoidiagramintheplane,inwhichthe generating points are generalized to circles and the distance is generalized to the Laguerredistance. Inthispaper,ananalogueoftheLaguerreVoronoidiagramis introduced on the sphere. The Laguerre distance from a point to a circle on the sphereisdeflnedasthegeodesiclengthofthetangentlinesegmentfromthepoint to the circle. This distance deflnes 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.,thecounterpartofastraightline),andtheVoronoiedgeisperpendic- ular to the great circle passing through the centers of the two generating circles. Furthermore,theconstructionofthisdiagramisreducedtotheconstructionofa three-dimensionalconvexhull,andthusaworst-caseoptimalO(nlogn)algorithm isobtained. Applicationsofthisdiagramincludethecomputationoftheunionof