Empty pentagons in point sets with collinearities

Janos Barat, Vida Dujmovic, Gwenael Joret, Michael Payne, Ludmila Scharf, Daria Schymura, Pavel Valtr, David Wood

Research output: Contribution to journalArticleResearchpeer-review

1 Citation (Scopus)

Abstract

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?2 points in the plane contains an empty pentagon or ? collinear points. This is optimal up to a constant factor since the (? - 1) x (? - 1) square lattice contains no empty pentagon and no ?collinear points. The previous best known bound was doubly exponential.
Original languageEnglish
Pages (from-to)198-209
Number of pages12
JournalSIAM Journal on Discrete Mathematics
Volume29
Issue number1
DOIs
Publication statusPublished - 2015

Keywords

  • Erd˝os problems
  • discrete geometry

Cite this