zbMATH — the first resource for mathematics

Empty simplices in Euclidean space. (English) Zbl 0639.52006
Let P be a set of n points in $${\mathbb{R}}^ d$$ in general position. A simplex spanned by $$d+1$$ distinct points of P is called empty if it contains no point of P in its interior. Let $$f_ d(P)$$ denote the number of empty simplices in P. Trivially, $$f_ d(P)\leq \left( \begin{matrix} n\\ d+1\end{matrix} \right)$$, with equality if P is the vertex set of a convex d-polytope. By a result of Katchalski and Meir, $$f_ d(P)\geq \left( \begin{matrix} n-1\\ d\end{matrix} \right).$$
The authors describe a random construction for P which proves $$f_ d(P)<K(d)\left( \begin{matrix} n\\ d\end{matrix} \right)$$, with K(d) a constant depending only on d. Several related questions are discussed.
Reviewer: E.Schulte

MSC:
 52A37 Other problems of combinatorial convexity 11K16 Normal numbers, radix expansions, Pisot numbers, Salem numbers, good lattice points, etc.
Keywords:
number of empty simplices
Full Text: