Finding sets of points without empty convex 6-gons

DOI10.1007/S00454-002-2829-XMaRDI QIDQ1864134zbMATH OpenOpenAlexWikidataFDO

Authors Mark H. Overmars

Publication date 17 March 2003

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00454-002-2829-x

zbMATH Keywords

convex hullempty convex \(6\)-gonsErdős problemsincremental algorithm

Mathematics Subject Classification ID

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

Review text

The author investigates a problem posed by Erdős which asks whether every large enough set of points in general position in the plane contains six points that form a convex \(6\)-gon without any points from the set in its interior. The author presents a fast incremental algorithm with which he was able to find a set of \(29\) points in the plane in general position which does not contain empty \(6\)-gons. In addition, using results obtained by the algorithm, a number of observations and conjectures are formulated about the possible structure of sets of points without empty convex \(6\)-gons.

Recommendations

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

Cited in

(28)

• Large convex holes in random point sets
• Largest and smallest area triangles on imprecise points
• On weighted sums of numbers of convex polygons in point sets
• A superlinear lower bound on the number of 5-holes
• On empty convex polygons in a planar point set
• On the Erdös-Szekeres problem
• Interior points in the Erdős-Szekeres theorems
• Almost empty hexagons
• Empty convex hexagons in planar point sets
• On the Erdős-Szekeres \(n\)-interior-point problem
• On the existence of a convex point subset containing one triangle in the plane
• The Erdős-Szekeres Problem
• On Erdős-Szekeres-type problems
• On the Erdős–Szekeres problem in combinatorial geometry
• On empty hexagons
• Specified holes with pairwise disjoint interiors in planar point sets
• A Minimal Planar Point Set with Specified Disjoint Empty Convex Subsets
• A SAT attack on Erdős-Szekeres numbers in \(\mathbb{R}^d\) and the empty hexagon theorem
• Convex hulls of random order types
• Every large point set contains many collinear points or an empty pentagon
• A SAT attack on higher dimensional Erdős-Szekeres numbers
• On disjoint holes in point sets
• Almost empty monochromatic polygons in planar point sets
• Holes in convex and simple drawings
• Two disjoint 5-holes in point sets
• On the minimum number of mutually disjoint holes in planar point sets
• Searching for empty convex polygons
• Cells in any simple polygon formed by a planar point set

This page was built for publication: Finding sets of points without empty convex 6-gons

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