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 [0, 1]^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 k3 and a set 𝒫 of n n points in [ 0, 1 ] 2 [0, 1]^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 ) Δ_k(n) , when the n n points in 𝒫 are chosen independently and uniformly at random in [ 0, 1 ] 2 [0, 1]^2 . We prove that Δ ˜ k ( n ) = Θ n − k k − 2 Δ_k(n)=Θ (n^-kk-2) , for every fixed k ≥ 3 k3 .