Planar sets with few empty convex polygons
Let \(g_i(n)\) be the minimum number of empty convex polygons with \(i\) vertices that is necessarily contained in any collection of \(n\) points in the plane, no three of them on a straight line (call this a generic collection of \(n\) points). For example \(g_4(n) \geq k\) means that any such collection of \(n\) points always contains at least \(k\) empty convex quadrilaterals. It has been known by a construction of Horton that \(g_i(n) = 0\) for \(i\geq 7\). For \(i\leq 5\) upper and lower bounds for \(g_i(n)\) are known and for \(g_6(n)\) only an upper bound is known, so that it is still an open problem whether any generic collection of \(n\) points contains an empty convex hexagon. In this paper improved upper bounds are given for \(g_i(n)\) for \(i=3,4,5,6\), as far as the multiplicative constants are concerned: \(g_3(n) \leq 1.683 n^2,\;g_4(n) \leq 2.132 n^2,\;g_5(n) \leq 1.228 n^2,\;g_6(n) \leq 0.297 n^2\).
- Convex independent sets and 7-holes in restricted planar point sets
- Finding convex sets among points in the plane
- Chromatic variants of the Erdős--Szekeres theorem on points in convex position.
- Drawing the Horton set in an integer grid of minimum size
- Planar sets containing no three collinear points and non-averaging sets of integers
- Empty rainbow triangles in \(k\)-colored point sets
- Faster counting empty convex polygons in a planar point set
- Empty monochromatic simplices
- On empty convex polygons in a planar point set
- Empty convex hexagons in planar point sets
- Empty squares in arbitrary orientation among points
- Large area convex holes in random point sets
- The number of empty four-gons in random point sets
- Almost empty monochromatic triangles in planar point sets
- Empty pentagons in point sets with collinearities
- Empty convex hexagons in planar point sets
- EMPTY CONVEX 5-GONS IN PLANAR POINT SETS
- scientific article; zbMATH DE number 4024179 (Why is no real title available?)
- The Erdos-Szekeres problem on points in convex position – a survey
- Almost empty polygons
- scientific article; zbMATH DE number 881170 (Why is no real title available?)
- A Minimal Planar Point Set with Specified Disjoint Empty Convex Subsets
- On empty convex polygons in a planar point set
- More on empty convex quadrilaterals in a planar point set
- Planar point sets with a small number of empty convex polygons
- Every large point set contains many collinear points or an empty pentagon
- Weights of convex quadrilaterals and empty triangles in weighted point sets
- Empty pseudo-triangles in point sets
- Empty monochromatic triangles
- On characterizing collections arising from N-gons in the plane
- Empty convex polygons in almost convex sets
- On the number of empty convex quadrilaterals of a finite set in the plane
This page was built for publication: Planar sets with few empty convex polygons
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2714367)
