Distributions of points in the unit square and large kk-gons

We consider a generalization of Heilbronn’s triangle problem by asking, given any integers n≥kn≥k, for the supremum Δk(n)Δk(n) of the minimum area determined by the convex hull of some kk of nn points in the unit square [0,1]2[0,1]2, where the supremum is taken over all distributions of nn points in [0,1]2[0,1]2. Improving the lower bound Δk(n)=Ω(1/n(k−1)/(k−2))Δk(n)=Ω(1/n(k−1)/(k−2)) from [C. Bertram-Kretzberg, T. Hofmeister, H. Lefmann, An algorithm for Heilbronn’s problem, SIAM Journal on Computing 30 (2000) 383–390] and from [W.M. Schmidt, On a problem of Heilbronn, Journal of the London Mathematical Society (2) 4 (1972) 545–550] for k=4k=4, we show that Δk(n)=Ω((logn)1/(k−2)/n(k−1)/(k−2))Δk(n)=Ω((logn)1/(k−2)/n(k−1)/(k−2)) for fixed integers k≥3k≥3 as asked for in [C. Bertram-Kretzberg, T. Hofmeister, H. Lefmann, An algorithm for Heilbronn’s problem, SIAM Journal on Computing 30 (2000) 383–390]. Moreover, we provide a deterministic polynomial time algorithm which finds nn points in [0,1]2[0,1]2, which achieve this lower bound on Δk(n)Δk(n).