In 1933, Esther Klein asked whether there was a function f(n) such that
every set of f(n) points in general position in the plane must contain the
vertices of a convex n-gon. Paul Erdös and György Szekeres answered this
question affirmatively by deriving the following bounds:
|
2n-2 + 1 < f(n) <
( |
|
) + 1
=
O(4n/sqrt{n})
|
(Esther Klein and György Szekeres were married soon after the upper bound was
proved; hence, Erdös referred to it as the "happy end theorem".) The lower bound is
sharp for all n<6, and Erdös and Szekeres conjectured that it is sharp for all
n.
These were the best bounds known for over 60 years. Finally, in 1996, Fan Chung and
Ron Graham improved the upper bound by 1:
This modest result apparently opened the floodgates to further improvement. Daniel
Kleitman and Lior Pachter soon improved the bound by 2n-7:
Inspired by these results, Géza Toth and Pavel Valtr improved the upper bound by
roughly a factor of two:
This is the current record. To quote Kleitman and Pachter:
[Chung and Graham's] modest improvement is like a drop of water that appears downstream
from a dam. This drop can be a harbinger of a trickle, then perhaps a stream, and finally
the dam may collapse with a rush of water. It is the purpose of [our] paper to replace
the Chung-Graham drop with a trickle. Géza Toth and Pavel Valtr have recently
replaced out trickle with a stream by further improving the upper bound.
Chung and Graham again conjectured that the lower bound 2n-2+1 is the
correct value of f(n). They offered a $100 reward for the first proof that
f(n) = O((4-c)n) for some positive constant c.
A similar question, raised by Erdös, is whether there is a function
g(n) such that any set of g(n) points in general position
contains the vertices of an empty convex n-gon, that is, a convex
n-gon with none of the points in its interior. It is easy to show that
g(3) = 2 and g(4) = 4; Harborth proved that
g(5) = 9. Horton proved the surprising result that g(7) is
infinite -- there are arbitrarily large sets of points in general
position with no empty convex 7-gons! The status of g(6) is still open. The
current best lower bound, due to Overmars, Scholten, and Vincent, is
g(6) > 28, but no finite upper bound is known.
Open Problems -
Jeff Erickson
(jeffe@cs.uiuc.edu)
23 Jul 1998