Empty Pentagons in Point Sets with Collinearities
2015
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 $328\ell^2$ points in the plane contains an empty pentagon or $\ell$ collinear points. This is optimal up to a constant factor since the $(\ell -1)\times(\ell-1)$ square lattice contains no empty pentagon and no $\ell$ collinear points. The previous best known bound was doubly exponential.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
0
References
2
Citations
NaN
KQI