An Algorithm for Heilbronn's Problem
Authors:
- Claudia Bertram--KretzbergCBClaudia Bertram--Kretzberg
- Thomas HofmeisterTHThomas Hofmeister
- Hanno LefmannHLHanno Lefmann
- 1 January 2000
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 30 (2) , 383-390
Abstract
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 Komlós, Pintz, and Szemerédi [ 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.
Keywords
This publication has 12 references indexed in Scilit:
- The Algorithmic Aspects of Uncrowded HypergraphsSIAM Journal on Computing, 1999
- Approximating maximum independent sets in uniform hypergraphs1998
- Derandomizing Chebyshev's inequality to find independent sets in uncrowded hypergraphsRandom Structures & Algorithms, 1996
- Extremal uncrowded hypergraphsJournal of Combinatorial Theory, Series A, 1982
- A Lower Bound for Heilbronn'S ProblemJournal of the London Mathematical Society, 1982
- On Heilbronn's Triangle ProblemJournal of the London Mathematical Society, 1981
- Developments in Heilbronn's triangle problemAdvances in Mathematics, 1976
- Turán's theorem for k-graphsDiscrete Mathematics, 1972
- On a Problem of Heilbronn†Journal of the London Mathematical Society, 1972
- On a Problem of HeilbronnJournal of the London Mathematical Society, 1951