For a fixed k, does there exist an n = n(k) such that any point set in the plane of size at least n(k) contains an empty convex polygon (a "hole") of size k ?Horton showed that no such n exists for k = 7. Specifically, for any n, there exists a set of n points in the plane that had no empty convex heptagon. Conversely, Bárány and Füredi showed that for k = 5, for sufficiently large n, any point set of size n had an empty convex pentagon.
For k = 6, the matter was unresolved, until just recently. This week's combinatorics seminar at NYU is by Andres Varon, who announces that Tobias Gerken has just closed this gap, showing that such an n exists for k = 6. If and when I get more details, I'll post them here.
Update: David Eppstein and Libertarianoid mention this as well. Libertarianoid has further details:
The conjecture was recently resolved by Tobias Gerken in affirmative. As Matousek says:
"P. 34, the 6-hole problem was resolved in 2005 by Tobias Gerken, who showed by a clever case analysis that any set containing 9 points in convex positions has a 6-hole. The proof was simplified by Pavel Valtr to about 4 pages (but one needs more than 9 points in convex position to start with, and hence the resulting upper bound for n(6) is worse)."
The original proof is somewhat long (around 39 pages), but elementary and not too hard to read. Valtr gave a talk on his simplified proof a while ago.
That's very nice. What's the story in 3-d? Are there arbitrarily large point sets for which the convex hull of any 5 points is a tetrahedron?
ReplyDeletePosted by Anonymous
--What's the story in 3-d? Are there arbitrarily large point sets for which the convex hull of any 5 points is a tetrahedron?
ReplyDeleteNo. Let S be any d+3 points in general position from R^d. Then there exists a subset S' of S of cardinality d+2 such that the convex hull of S' contains no point of S' in its interior.
Posted by Anonymous