Distributions of Points and Large Quadrangles

摘要

We consider a variant of Heilbronn's triangle problem by asking, given any integer n ≥ 4, for the supremum Δ_4(n) of the minimum area determined by the convex hull of some four of n points in the unit-square [0,1]~2 over all distributions of n points in [0,1]~2. Improving the lower bound Δ_4(n) = Ω(1/n~(3/2)) of Schmidt [19], we will show that Δ_4(n) = Ω((log n)~(1/2)/n~(3/2)) as asked for in [5], by providing a deterministic polynomial time algorithm which finds n points in the unit-square [0,1]~2 that achieve this lower bound.