%0 Journal Article
%T Empty pentagons in point sets with collinearities
%A J¨˘nos Bar¨˘t
%A Vida DujmoviŁż
%A GwenaŁżl Joret
%A Michael S. Payne
%A Ludmila Scharf
%A Daria Schymura
%A Pavel Valtr
%A David R. Wood
%J Computer Science
%D 2012
%I arXiv
%R 10.1137/130950422
%X An empty pentagon in a point set P in the plane is a set of five points in P in strictly convex position with no other point of P in their convex hull. We prove that every finite set of at least 328k^2 points in the plane contains an empty pentagon or k collinear points. This is optimal up to a constant factor since the (k-1)x(k-1) grid contains no empty pentagon and no k collinear points. The previous best known bound was doubly exponential.
%U http://arxiv.org/abs/1207.3633v1