An algorithm for Heilbronn's problem

Heilbronn conjectured that given arbitrary n points from the 2-dimensional unit square, there must be three points which form a triangle of area at most O(1/n(2)). This conjecture was disproved by a nonconstructive argument of Komlos, Pintz, and Szemeredi [J. London Math. Soc., 25 (1982), pp. 13-24] who showed that for every n there is a configuration of n points in the unit square where all triangles have area at least Omega(log n/n(2)). Considering a discretization of Heilbronn's problem, we give an alternative proof of the result from [ J. London Math. Soc., 25 (1982), pp. 13-24]. Our approach has two advantages: First, it yields a polynomial-time algorithm which for every n computes a configuration of n points where all triangles have area Omega(log n/n(2)). Second, it allows us to consider a generalization of Heilbronn's problem to convex hulls of k points where we can show that an algorithmic solution is also available.