university website

Abel, Z. (Zachary), Ballinger, B. (Brad), P. Bose (Prosenjit), Collette, S. (Sébastien), V. Dujmović (Vida), Hurtado, F. (Ferran), Kominers, S.D. (Scott Duke), Langerman, S. (Stefan), Pór, A. (Attila) and D. Wood (David)

2011

Every Large Point Set contains Many Collinear Points or an Empty Pentagon

Publication

Publication

Graphs and Combinatorics , Volume 27 - Issue 1 p. 47- 60

We prove the following generalised empty pentagon theorem for every integer ℓ ≥ 2, every sufficiently large set of points in the plane contains ℓ collinear points or an empty pentagon. As an application, we settle the next open case of the "big line or big clique" conjecture of Kára, Pór, and Wood [Discrete Comput. Geom. 34(3):497-506, 2005].

Additional Metadata
Keywords Big line or big clique conjecture, Empty hexagon, Empty pentagon, Empty quadrilateral, Erdo{double acute}s-Szekeres theorem, Happy end problem
Persistent URL doi.org/10.1007/s00373-010-0957-2
Journal Graphs and Combinatorics
Organisation School of Computer Science
Citation
Abel, Z. (Zachary), Ballinger, B. (Brad), Bose, P, Collette, S. (Sébastien), Dujmović, V, Hurtado, F. (Ferran), … Wood, D. (2011). Every Large Point Set contains Many Collinear Points or an Empty Pentagon. Graphs and Combinatorics, 27(1), 47–60. doi:10.1007/s00373-010-0957-2


User Publication Person Organisation Collection
Close