On Heilbronn triangle-type problems in higher dimensions

Main Article Content

Fabricio Siqueira Benevides Carlos Hoppen Hanno Lefmann Knut Odermann


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$.

Article Details

How to Cite
Benevides, F., Hoppen, C., Lefmann, H., & Odermann, K. (2019). On Heilbronn triangle-type problems in higher dimensions. Acta Mathematica Universitatis Comenianae, 88(3), 443-450. Retrieved from http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1276/678