An algorithm for Heilbronn's problem

Heilbronn conjectured that given arbitrary n points form R"2, located in the unit square (or circle), there must be three points which form a triangle of area at most O(1/n"2). This conjecture was proved false by a nonconstructive argument of Komlos, Pintz and Szemeredi [KPS] wo showed that there is a configuration of n points in the unit square where all triangles have area at least #OMEGA#(log n/n"2). In this paper, we provide a polynomial-time algorithm which for every n computes such as configuration of points. We then consider a generalization of this problem as introduced by Schmidt [Sc] to convex hulls of k #>=#4 points. We obtain the following result: for every k, there is a polynomial-time algorithm which on input n computes n points in the unit square such that the convex hull of any k points has area at least #OMEGA#(1/n"("k"-")"/"("k"-"2")). For k=4, the existence of such a configuration has been proved in [Sc]. (orig.)Available from TIB Hannover: RR 8071(97-1)+a / FIZ - Fachinformationszzentrum Karlsruhe / TIB - Technische InformationsbibliothekSIGLEDEGerman