Voronoi Diagrams of Arbitrary Order on the Sphere

Mercè Claverol; Andrea de las Heras Parrilla; Clemens Huemer

paper

Voronoi Diagrams of Arbitrary Order on the Sphere

arXiv:2207.13788

Abstract

For a given set of points $U$ on a sphere $S$ , the order $k$ spherical Voronoi diagram $S V_{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 $S V_{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 $S V_{k} (U)$ . These formulas were not known before. We obtain several more properties for $S V_{k} (U)$ , and we also show that $S V_{k} (U)$ has a small orientable cycle double cover.