Let $X={x_1,ldots,x_n} subset mathbb R^d$ be an $n$-element point set in general position. For a $k$-element subset ${x_{i_1},ldots,x_{i_k}} subset X$ let the degree ${rm deg}_k(x_{i_1},ldots,x_{i_k})$ be the number of empty simplices ${x_{i_1},ldots,x_{i_{d+1}}} subset X$ containing no other point of $X$. The $k$-degree of the set $X$, denoted ${rm 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 ${rm deg}_d(X)=Theta(n)$, improving results previously obtained by Barany, 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 ${rm deg}_k(X)$. In the case $k=1$ we prove that ${rm deg}_1(X)=Theta(n^{d-1})$.
تحميل البحث