Empty pentagons in point sets with collinearities

DOI10.1137/130950422zbMATH Open1329.52014arXiv1207.3633OpenAlexW3099884977MaRDI QIDQ3453574FDOQ3453574

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)

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.

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

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

zbMATH Keywords

discrete geometrycollinear pointsempty pentagonErdös problems

Mathematics Subject Classification ID

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

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)