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

ABSTRACT

We consider a generalization of Heilbronn's triangle problem by asking, given any integers n ≥ k ≥ 3, 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]², where the supremum is taken over all distributions of n points in [0, 1]². Improving the lower bound Δk(n) = Ω(1/n^(k-1)/(k-2}) from [5] and from [20] for k = 4, we will show that Δk(n) = Ω((log n)^1/(k-2)/n^(k-1)/(k-2) for each fixed integer k ≥ 3 as asked for in [5]. We will also provide a deterministic polynomial time algorithm which finds n points in the unit-square [0, 1]² achieving this lower bound.

REFERENCES

• 1: M. Ajtai, J. Komtós, J. Pintz, J. Spencer and E. Szemerédi, Extremal Uncrowded Hypergraphs, Journal of Combinatorial Theory Ser. A, 32, 1982, 321--335.
• 2: Gill Barequet, A Lower Bound for Heilbronn's Triangle Problem in d Dimensions, SIAM Journal on Discrete Mathematics, v.14 n.2, p.230-236, 2001 [doi>10.1137/S0895480100365859]
• 3: G. Barequet, The On-Line Heilbronn's Triangle Problem, Discrete Mathematics, 283, 2004, 7--14.
• 4: Claudia Bertram-Kretzberg , Hanno Lefmann, The Algorithmic Aspects of Uncrowded Hypergraphs, SIAM Journal on Computing, v.29 n.1, p.201-230, Feb. 2000 [doi>10.1137/S0097539797323716]
• 5: Claudia Bertram--Kretzberg , Thomas Hofmeister , Hanno Lefmann, An Algorithm for Heilbronn's Problem, SIAM Journal on Computing, v.30 n.2, p.383-390, 2000 [doi>10.1137/S0097539798348870]
• 6: P. Brass, An Upper Bound for the d-Dimensional Heilbronn Triangle Problem, preprint, 2003.
• 7: Richard A. Duke , Hanno Lefmann , Vojtěch Rödl, On uncrowded hypergraphs, Random Structures & Algorithms, v.6 n.2-3, p.209-212, March-May 1995
• 8: A. Fundia, Derandomizing Chebychev's Inequality to find Independent Sets in Uncrowded Hypergraphs, Random Structures & Algorithms, 8, 1996, 131--147.
• 9: Tao Jiang , Ming Li , Paul Vitányi, The average-case area of Heilbronn-type triangles, Random Structures & Algorithms, v.20 n.2, p.206-219, March 2002 [doi>10.1002/rsa.10024]
• 10: J. Komlós, J. Pintz and E. Szemerédi, On Heilbronn's Triangle Problem, Journal of the London Mathematical Society, 24, 1981, 385--396.
• 11: J. Komlós, J. Pintz and E. Szemerédi, A Lower Bound for Heilbronn's Problem, Journal of the London Mathematical Society, 25, 1982, 13--24.
• 12: H. Lefmann, Distributions of Points and Large Quadrangles, to appear in ISAAC'2004.
• 13: Hanno Lefmann, On Heilbronn’s Problem in Higher Dimension, Combinatorica, v.23 n.4, p.669-680, December 2003 [doi>10.1007/s00493-003-0040-1]
• 14: Hanno Lefmann , Niels Schmitt, A Deterministic Polynomial-Time Algorithm for Heilbronn's Problem in Three Dimensions, SIAM Journal on Computing, v.31 n.6, p.1926-1947, 2002 [doi>10.1137/S0097539701395115]
• 15: K. F. Roth, On a Problem of Heilbronn, Journal of the London Mathematical Society 26, 1951, 198--204.
• 16: K. F. Roth, On a Problem of Heilbronn, II, Proc. of the London Mathematical Society (3), 25, 1972, 193--212.
• 17: K. F. Roth, On a Problem of Heilbronn, III, Proc. of the London Mathematical Society (3), 25, 1972, 543--549.
• 18: K. F. Roth, Estimation of the Area of the Smallest Triangle Obtained by Selecting Three out of n Points in a Disc of Unit Area, Proc. of Symposia in Pure Mathematics, 24, 1973, AMS, Providence, 251--262.
• 19: K. F. Roth, Developments in Heilbronn's Triangle Problem, Advances in Mathematics, 22, 1976, 364--385.
• 20: W. M. Schmidt, On a Problem of Heilbronn, Journal of the London Mathematical Society (2), 4, 1972, 545--550.