Stars of empty simplices

DOI10.1215/00192082-11081246MaRDI QIDQ6200587zbMATH OpenOpenAlexFDO

Authors Matthias Reitzner, Daniel Temesvari

Publication date 22 March 2024

Published in Illinois Journal of Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1808.08734, https://projecteuclid.org/journals/illinois-journal-of-mathematics/volume-68/issue-1/Stars-of-empty-simplices/10.1215/00192082-11081246.full

zbMATH Keywords

empty simplexrandom points in a convex body

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) Erd?s problems and related topics of discrete geometry (52C10) Geometric probability and stochastic geometry (60D05)

Abstract: Let $X=x_1,ldots,x_{n}subsetmathbb{R}^d$ be an $n$-element point set in general position. For a $k$-element subset $x_{i_1},ldots,x_{i_k}subsetX$ let the degree ${mdeg}_k(x_{i_1},ldots,x_{i_k})$ be the number of empty simplices $x_{i_1},ldots,x_{i_{d+1}}subsetX$ containing no other point of $X$. The $k$-degree of the set $X$, denoted ${mdeg}_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 ${mdeg}_d(X)=Theta(n)$, improving results previously obtained by B'ar'any, 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 ${mdeg}_k(X)$. In the case $k=1$ we prove that ${mdeg}_1(X)=Theta(n^{d-1})$.

Review text

For a finite set \(X\subset{\mathbb R}^d\) in general position and distinct \(x_1,\dots,x_d\in X\), let \[ \operatorname{deg}_d(x_1,\dots,x_d;X):= \sum_{x_{d+1}\in X\setminus\{x_1,\dots,x_d\}} \1 \{\mathrm{int}\,\mathrm{conv}\{x_1,\dots,x_{d+1}\}\cap X=\emptyset\}.\] The number \(\operatorname{deg}_d(X):= \max \operatorname{deg}_d(x_1,\dots,x_d;X)\), where the \(\max\) is over the \(d\)-element subsets of \(X\), is here studied for random points. A first theorem says the following. Let \(X_n\) be a set of \(n\) independent, uniform random points in a convex body \(K\subset{\mathbb R}^d\). There exists a constant \(c(d,K)>0\) such that \(c(d,K)n\le {\mathbb E}\, \operatorname{deg}_d(X_n)\le n\). (Numerical computations suggest that the optimal constant may be surprisingly large.) Next, let \(N_\Delta(X)\) be the total number of empty simplices defined by \(X\). The authors are able to determine the precise asymptotic behavior of \({\mathbb E}\,N_\Delta(X_n)\) (with \(X_n\) as above) as \(n\to\infty\), and they provide lower and upper bounds for \(N_\Delta(X_n)\) of order \(n^d\) that are independent of \(K\). The number \(\operatorname{deg}_d(X)\) (introduced by Erdös) is generalized, for \(k=1,\dots,d\), to \(\operatorname{deg}_k(X):= \max\operatorname{deg}_k(x_1,\dots,x_k;X)\), where the \(\max\) is over all \(k\)-element subsets \(\{x_1,\dots,x_k\}\subset X\) and \(\operatorname{deg}_k(x_1,\dots,x_k;X)\), for such a subset \(\{x_1,\dots,x_k\}\), is the number of empty simplices defined by \(X\) that contain this subset. For \(k=1\), the following results are obtained (there is a conjecture for general \(k\)). Let \(X_n\) be as above. There are constants \(c(d)\), \(c(d,K)\) such that \(c(d)n^{d-1} \le{\mathbb E}\,\operatorname{deg}_1(X_n)\le c(d,K)n^{d-1}\) for \(d>2\) and \(c(2)n\le {\mathbb E}\,\operatorname{deg}_1(X_n)\le c(2,K)n\ln^{\frac{1}{2}}n\) for \(d=2\).

Recommendations

• Moments of the maximal number of empty simplices of a random point set
• Empty Simplices in Euclidean Space
• Many empty triangles have a common edge
• On the expected number of k-sets
• scientific article; zbMATH DE number 3907270

Cites work

• Empty Simplices in Euclidean Space
• Gaussian polytopes: variances and limit theorems
• scientific article; zbMATH DE number 3905681 (Why is no real title available?)
• scientific article; zbMATH DE number 1786502 (Why is no real title available?)
• scientific article; zbMATH DE number 881170 (Why is no real title available?)
• Many empty triangles have a common edge
• Martingale inequalities and the jackknife estimate of variance
• Moments of the maximal number of empty simplices of a random point set
• Planar point sets with a small number of empty convex polygons
• Random polytopes
• Rates of Poisson convergence for U-statistics
• Research Problems in Discrete Geometry
• Short distances, flat triangles and Poisson limits
• Stochastic and Integral Geometry
• Upper (lower) bounds on the mean of the maximum (minimum) of a number of random variables

Cited in

(1)

• Holes and Islands in Random Point Sets

This page was built for publication: Stars of empty simplices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6200587)