Voronoi Diagrams of Arbitrary Order on the Sphere

07/27/2022

∙

by   Mercè Claverol, et al.

∙

0

∙

share

For a given set of points U on a sphere S, the order k spherical Voronoi diagram SV_k(U) decomposes the surface of S into regions whose points have the same k nearest points of U. Hyeon-Suk Na, Chung-Nim Lee, and Otfried Cheong (Comput. Geom., 2002) applied inversions to construct SV_1(U). We generalize their construction for spherical Voronoi diagrams from order 1 to any order k. We use that construction to prove formulas for the numbers of vertices, edges, and faces in SV_k(U). These formulas were not known before. We obtain several more properties for SV_k(U), and we also show that SV_k(U) has a small orientable cycle double cover.