On Spheres with $k$ Points Inside

We generalize the classic definition of Delaunay triangulation and prove that for a locally finite and coarsely dense generic point set, $A\subseteq {\mathbb{R}}^d$, the $d$-simplices whose vertices belong to $A$ and whose circumscribed spheres enclose exactly $k$ points of $A$ cover ${\mathbb{R}}^d$ exactly $\left(\genfrac{}{}{0px}{}{d+k}{d}\right)$ times. Similarly, the subset of such simplices incident to a point in $A$ cover any small enough neighborhood of that point exactly $\left(\genfrac{}{}{0px}{}{d+k-1}{d-1}\right)$ times. We extend this result to the cases in which the points are weighted and when $A$ contains only finitely many points in ${\mathbb{R}}^d$ or in ${\mathbb{S}}^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.