Heilbronn triangle‐type problems in the unit square [0, 1]2. Issue 3 (25th July 2022) - Benevides, Fabricio S.; Hoppen, Carlos; Lefmann, Hanno; Odermann, Knut
Abstract: The Heilbronn triangle problem is a classical geometrical problem that asks for a placement of n $$ n $$ points in the unit square [ 0, 1 ] 2 $$ {\left[0, 1\right]}^2 $$ that maximizes the smallest area of a triangle formed by three of those points. This problem has natural generalizations. For an integer k ≥ 3 $$ k\ge 3 $$ and a set 𝒫 of n $$ n $$ points in [ 0, 1 ] 2 $$ {\left[0, 1\right]}^2 $$, let A k ( 𝒫 ) be the minimum area of the convex hull of k $$ k $$ points in 𝒫 . Here, instead of considering the supremum of A k ( 𝒫 ) over all such choices of 𝒫, we consider its average value, Δ ˜ k ( n ) $$ {\tilde{\Delta}}_k(n) $$, when the n $$ n $$ points in 𝒫 are chosen independently and uniformly at random in [ 0, 1 ] 2 $$ {\left[0, 1\right]}^2 $$ . We prove that Δ ˜ k ( n ) = Θ n − k k − 2 $$ {\tilde{\Delta}}_k(n)=\Theta \left({n}^{\frac{-k}{k-2}}\right) $$, for every fixed k ≥ 3 $$ k\ge 3 $$ .