On Heilbronn triangle-type problems in higher dimensions

Abstract

The Heilbronn triangle problem is a classical geometrical problem that asks for a placement of $n$ points in the unit-square $[0,1]^2$, that maximizes the smallest area of a triangle formed by those points. This problem has natural generalizations to higher dimensions. For integers $k, d \ge 2$ and a set $\mathcal P$ of $n$ points in $[0,1]^d$, let $s = \min\{(k-1),d\}$ and $V_k^{(d)}({\mathcal P})$ be the minimum $s$-dimensional volume of the convex hull of $k$ points in $\mathcal P$. Here, instead of considering the supremum of $V_k^{(d)}({\mathcal P})$, we consider its average value, $\avrg{\Delta}_k^{(d)}(n)$, when the $n$ points in $\mathcal P$ are chosen independently and uniformly at random in $[0,1]^d$. We prove that $\avrg{\Delta}_k^{(d)}(n) = \Theta \left(n^{\frac{-k}{1+|d-k+1|}}\right)$, for every fixed $k, d \ge 2$.