Heilbronn triangle‐type problems in the unit square [0, 1]2. Issue 3 (25th July 2022)

• Record Type: Journal Article
• Authors: Benevides, Fabricio S.; Hoppen, Carlos; Lefmann, Hanno; Odermann, Knut
• Is Part Of: Random structures & algorithms. Volume 62:Issue 3(2023)
• Page Start: 585
• Page End: 599
• Publication Date: 2022-07-25
• Subjects: area -- convex hull -- geometry -- Heilbronn; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.21109
• Languages: English
• ISSNs: 1042-9832

Abstract

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