2024/08/17 by John Edwards, Edwards, John, Tracy L. Payne +3
Mathematics · Physics and Astronomy · #51F99 #Advanced Differential Geometry Research #Advanced Topics in Algebra #FOS: Mathematics #I.3.5 #Mathematics and Applications #Metric Geometry (math.MG)
paper · pdf · doi:10.48550/arxiv.2408.09279
openalex publication_date 2024/08/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We use Lie sphere geometry to describe two large categories of generalized Voronoi diagrams that can be encoded in terms of the Lie quadric, the Lie inner product, and polyhedra. The first class consists of diagrams defined in terms of extremal spheres in the space of Lie spheres, and the second class includes minimization diagrams for functions that can be expressed in terms of affine functions on a higher-dimensional space. These results unify and generalize previous descriptions of generalized Voronoi diagrams as convex hull problems. Special cases include classical Voronoi diagrams, power diagrams, order k and farthest point diagrams, Apollonius diagrams, medial axes, and generalized Voronoi diagrams whose sites are combinations of points, spheres and half-spaces. We describe the application of these results to algorithms for computing generalized Voronoi diagrams and find the complexity of these algorithms.