Every large point set contains many collinear points or an empty pentagon

DOI10.1007/S00373-010-0957-2zbMATH Open1236.52013arXiv0904.0262OpenAlexW3100935002MaRDI QIDQ659671FDOQ659671

Authors: Brad Ballinger, Prosenjit Bose, Sébastien Collette, Vida Dujmović, Ferran Hurtado, Scott Duke Kominers, Stefan Langerman, Attila Pór, David R. Wood, Zachary R. Abel 

Publication date: 24 January 2012

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Abstract: We prove the following generalised empty pentagon theorem: for every integer $ellgeq2$, every sufficiently large set of points in the plane contains $ell$ collinear points or an empty pentagon. As an application, we settle the next open case of the "big line or big clique" conjecture of K'ara, P'or, and Wood [emph{Discrete Comput. Geom.} 34(3):497--506, 2005].

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

Recommendations

• Empty pentagons in point sets with collinearities
• Almost empty polygons
• Empty convex hexagons in planar point sets
• Large bichromatic point sets admit empty monochromatic 4-gons
• The empty hexagon theorem

zbMATH Keywords

convex positionempty hexagonbig line or big clique conjecturecollinear pointsempty pentagonErdős-Szekeres theorem

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Erd?s problems and related topics of discrete geometry (52C10) Variants of convex sets (star-shaped, ((m, n))-convex, etc.) (52A30)

Cites Work

• Research Problems in Discrete Geometry
• On visibility and blockers
• Planar sets with few empty convex polygons
• Title not available (Why is that?)
• Planar point sets with a small number of empty convex polygons
• Title not available (Why is that?)
• Konvexe Fünfecke in ebenen Punktmengen
• The empty hexagon theorem
• Empty convex hexagons in planar point sets
• On empty hexagons
• Sets with No Empty Convex 7-Gons
• Almost empty polygons
• Title not available (Why is that?)
• The Erdos-Szekeres problem on points in convex position – a survey
• On some metric and combinatorial geometric problems
• On some problems of elementary and combinatorial geometry
• Maximal Independent Subsets in Steiner Systems and in Planar Sets
• Convex independent sets and 7-holes in restricted planar point sets
• Drawings of planar graphs with few slopes and segments
• Large empty convex polygons in \(k\)-convex sets
• On empty convex polygons in a planar point set
• Searching for empty convex polygons
• A sufficient condition for the existence of large empty convex polygons
• On the chromatic number of the visibility graph of a set of points in the plane
• Constructions from empty polygons
• Empty convex polygons in almost convex sets
• On the existence of a convex point subset containing one triangle in the plane
• Finding sets of points without empty convex 6-gons
• Blocking visibility for points in general position
• New proofs about the number of empty convex 4-gons and 5-gons in a planar point set
• Happy endings for flip graphs
• Reconfirmation of Two Results on Disjoint Empty Convex Polygons
• Title not available (Why is that?)
• On the number of empty convex quadrilaterals of a finite set in the plane

Cited In (5)

• On planar point sets with the pentagon property
• Flip distance between triangulations of a simple polygon is NP-complete
• Empty pentagons in point sets with collinearities
• On the connectivity of visibility graphs
• Flip distance between triangulations of a planar point set is APX-hard

This page was built for publication: Every large point set contains many collinear points or an empty pentagon

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