Distributions of points in the unit square and large -gons

We consider a generalization of Heilbronn’s triangle problem by asking, given any integers n ≥ k , for the supremum Δ k ( n ) of the minimum area determined by the convex hull of some k of n points in the unit square [ 0 , 1 ] 2 , where the supremum is taken over all distributions of n points in [ 0 , 1 ] 2 . Improving the lower bound Δ 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 = 4 , we show that Δ k ( n ) = Ω ( ( log n ) 1 / ( k − 2 ) / n ( k − 1 ) / ( k − 2 ) ) for fixed integers k ≥ 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 n points in [ 0 , 1 ] 2 , which achieve this lower bound on Δ k ( n ) .