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

DOI10.1007/S00373-010-0957-2MaRDI QIDQ659671zbMATHOpenAlexFDO

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)

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

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)

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

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

Cites work

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

Cited in

(5)

• On the connectivity of visibility graphs
• A Note on Visible Islands
• On planar point sets with the pentagon property
• Flip distance between triangulations of a planar point set is APX-hard
• Empty pentagons in point sets with collinearities

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)