Stars of Empty Simplices

Abstract

Let $X=\{x_1,\dots ,x_n\}\subset {\mathbb{R}}^d$ be an $n$-element point set in general position. For a $k$-element subset $\{x_{i_1},\dots ,x_{i_k}\}\subset X$ let the degree ${\mathrm{deg}}_k(x_{i_1},\dots ,x_{i_k})$ be the number of empty simplices $\{x_{i_1},\dots ,x_{i_{d+1}}\}\subset X$ containing no other point of $X$. The $k$-degree of the set $X$, denoted ${\mathrm{deg}}_k(X)$, is defined as the maximum degree over all $k$-element subset of $X$. We show that if $X$ is a random point set consisting of $n$ independently and uniformly chosen points from a compact set $K$ then ${\mathrm{deg}}_d(X)=\Theta (n)$, improving results previously obtained by Bárány, Marckert and Reitzner [Many empty triangles have a common edge, Discrete Comput. Geom., 2013] and Temesvari [Moments of the maximal number of empty simplices of a random point set, Discrete Comput. Geom., 2018] and giving the correct order of magnitude with a significantly simpler proof. Furthermore, we investigate ${\mathrm{deg}}_k(X)$. In the case $k=1$ we prove that ${\mathrm{deg}}_1(X)=\Theta (n^{d-1})$.

19 Pages. An error in the statement and proof of a Theorem in the previous version has been corrected