On Spheres with k Points Inside

2024/10/28 by Edelsbrunner, Herbert, Garber, Alexey, Saghafian, Morteza
#Combinatorics (math.CO) #Computational Geometry (cs.CG) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.2410.21204

Abstract

We generalize the classic definition of Delaunay triangulation and prove that for a locally finite and coarsely dense generic point set, A ⊆ ℝ^d, the d-simplices whose vertices belong to A and whose circumscribed spheres enclose exactly k points of A cover ℝ^d exactly \binomd+kd times. Similarly, the subset of such simplices incident to a point in A cover any small enough neighborhood of that point exactly \binomd+k-1d-1 times. We extend this result to the cases in which the points are weighted and when A contains only finitely many points in ℝ^d or in \mathbbS^d. Using these results, we give new proofs of classic results on k-facets, old and new combinatorial results for hyperplane arrangements, and a new proof for the fact that the volumes of hypersimplices are Eulerian numbers.

Related

• Families of similar simplices inscribed in most smoothly embedded spheres
• Empty Monochromatic Simplices
• On compact packings of Euclidean space with spheres of finitely many sizes
• Bounds on Embeddings of Triangulations of Spheres
• Covering points by hyperplanes and related problems