Properties for Voronoi diagrams of arbitrary order on the sphere

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. We study properties for SV_k(U), using different tools: the geometry of the sphere, a labeling for the edges of SV_k(U), and the inversion transformation. 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). Among the properties of SV_k(U), we also show that SV_k(U) has a small orientable cycle double cover.Postprint (published version