Empty pentagons in point sets with collinearities

DOI10.1137/130950422MaRDI QIDQ3453574zbMATH OpenOpenAlexFDO

Authors János Barát, Vida Dujmović, Gwenaël Joret, Michael S. Payne, Ludmila Scharf, Daria Schymura, Pavel Valtr, David R. Wood

Publication date 27 November 2015

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1207.3633

zbMATH Keywords

discrete geometrycollinear pointsempty pentagonErdös problems

Mathematics Subject Classification ID

Erd?s problems and related topics of discrete geometry (52C10)

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 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.

Recommendations

• Every large point set contains many collinear points or an empty pentagon
• Almost empty polygons
• Disjoint empty convex pentagons in planar point sets
• On the number of pseudo-empty convex pentagons for a planar point set
• Planar sets with few empty convex polygons

Cited in

(4)

• On the number of pseudo-empty convex pentagons for a planar point set
• Disjoint empty convex pentagons in planar point sets
• On planar point sets with the pentagon property
• Every large point set contains many collinear points or an empty pentagon

This page was built for publication: Empty pentagons in point sets with collinearities

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3453574)