Empty Pentagons in Point Sets with Collinearities

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 arrow up $ points in the plane contains an empty pentagon or $\ell$ collinear points. This...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on discrete mathematics 2015-01, Vol.29 (1), p.198-209
Main Authors: Barát, János, Dujmović, Vida, Joret, Gwenaël, Payne, Michael S., Scharf, Ludmila, Schymura, Daria, Valtr, Pavel, Wood, David R.
Format: Article
Language:English
Subjects:
Collinearity
Constants
Convexity
Hulls (structures)
Lattices
Mathematical analysis
Optimization
Planes
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 arrow up $ 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.
ISSN:0895-4801
1095-7146
DOI:10.1137/130950422