Voronoi Diagrams of Arbitrary Order on the Sphere

2022/07/27 by Mercè Claverol Aguas, Claverol, Mercè, Andrea de las Heras Parrilla +3 · 1 citation
Computer Science · Environmental Science · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #Remote Sensing and LiDAR Applications #Topological and Geometric Data Analysis

paper · pdf · doi:10.48550/arxiv.2207.13788

openalex publication_date 2022/07/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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₁(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.

Cited by

• Separating dots with circles

Related

• Generalized Voronoi Diagrams and Lie Sphere Geometry
• Recognition of the Spherical Laguerre Voronoi Diagram
• A Voronoi poset
• The edge labeling of higher order Voronoi diagrams
• Classifying Voronoi graphs of hex spheres