Computer solution of the almost empty hexagon problem

DOI10.1134/S0001434611030163MaRDI QIDQ650447zbMATH OpenFDO

Authors V. A. Koshelev

Publication date 25 November 2011

Published in Mathematical Notes (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1134/S0001434611030163

zbMATH Keywords

almost empty hexagonempty hexagonErdős-Szekeres problemexhaustive searchpoints in general position in the planesignature

Mathematics Subject Classification ID

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

Review text

For any integer \(n\geq 3\) and \(k\geq 0\), let \(h(n,k)\) denote the smallest positive integer such that any set of at least \(h(n,k)\) points in general position in the plane has a subset of \(n\) points forming a convex \(n\)-gon, whose interior contains at most \(k\) of the points. The paper evaluates \(h(n,k)\) exactly for all \(n\leq 6\), except \(h(6,0)\), using a computer. These results refute a claim from the paper [\textit{H. Nyklová}, Stud. Sci. Math. Hung. 40, No. 3, 269--286 (2003; Zbl 1050.52006)].

Recommendations

• The empty hexagon theorem
• Empty convex hexagons in planar point sets
• Almost empty hexagons
• On empty hexagons
• Empty convex hexagons in planar point sets

Cites work

• Computer solution to the 17-point Erdős-Szekeres problem
• Sets with No Empty Convex 7-Gons
• The Erdos-Szekeres problem on points in convex position – a survey

Cited in

(5)

• The empty hexagon theorem
• The Erdős-Szekeres Problem
• Almost empty monochromatic triangles in planar point sets
• scientific article; zbMATH DE number 800308 (Why is no real title available?)
• Solving 7 7 hex with domination, fill-in, and virtual connections

This page was built for publication: Computer solution of the almost empty hexagon problem

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