On k-gons and k-holes in point sets

DOI10.1016/J.COMGEO.2014.12.007MaRDI QIDQ899713zbMATH OpenOpenAlexDBLPWikidataFDO

Authors R. Fabila-Monroy, Hernán González-Aguilar, T. Hackl, Marco A. Heredia, Clemens Huemer, Pavel Valtr, Birgit Vogtenhuber, Oswin Aichholzer, J. Urrutia

Publication date 30 December 2015

Published in Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

\(k\)-gons\(k\)-holesempty \(k\)-gonsErdős-Szekeres type problems

Mathematics Subject Classification ID

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

Abstract: We consider a variation of the classical ErdH{o}s-Szekeres problems on the existence and number of convex $k$-gons and $k$-holes (empty $k$-gons) in a set of $n$ points in the plane. Allowing the $k$-gons to be non-convex, we show bounds and structural results on maximizing and minimizing their numbers. Most noteworthy, for any $k$ and sufficiently large $n$, we give a quadratic lower bound for the number of $k$-holes, and show that this number is maximized by sets in convex position.

Recommendations

• 4-holes in point sets
• On 5-gons and 5-holes
• On Erdős-Szekeres-type problems for \(k\)-convex point sets
• On Erdős-Szekeres-type problems for \(k\)-convex point sets
• Lower bounds for the number of small convex \(k\)-holes

Cites work

• 4-holes in point sets
• A note on the number of empty triangles
• Computer solution to the 17-point Erdős-Szekeres problem
• Convex independent sets and 7-holes in restricted planar point sets
• Counting plane graphs: perfect matchings, spanning cycles, and Kasteleyn's technique
• Crossing Number Problems
• Empty convex hexagons in planar point sets
• scientific article; zbMATH DE number 3649571 (Why is no real title available?)
• scientific article; zbMATH DE number 3168302 (Why is no real title available?)
• scientific article; zbMATH DE number 4024179 (Why is no real title available?)
• scientific article; zbMATH DE number 5019923 (Why is no real title available?)
• scientific article; zbMATH DE number 3354154 (Why is no real title available?)
• scientific article; zbMATH DE number 3019031 (Why is no real title available?)
• Konvexe Fünfecke in ebenen Punktmengen
• Lower bounds for the number of small convex \(k\)-holes
• Lower bounds on the number of crossing-free subgraphs of \(K_N\)
• On 5-gons and 5-holes
• On empty convex polygons in a planar point set
• Planar point sets with a small number of empty convex polygons
• Research Problems in Discrete Geometry
• Sets with No Empty Convex 7-Gons
• The empty hexagon theorem
• Triangulations. Structures for algorithms and applications

Cited in

(19)

• On sets of \(n\) points in general position that determine lines that can be pierced by \(n\) points
• On almost empty monochromatic triangles and convex quadrilaterals in colored point sets
• Empty triangles in complete topological graphs
• 4-holes in point sets
• The number of empty four-gons in random point sets
• A note on the number of general 4-holes in (perturbed) grids
• Almost empty monochromatic triangles in planar point sets
• scientific article; zbMATH DE number 3961669 (Why is no real title available?)
• On 5-gons and 5-holes
• Maximum rectilinear convex subsets
• Specified holes with pairwise disjoint interiors in planar point sets
• Holes in 2-convex point sets
• Holes in 2-convex point sets
• Erdős-Szekeres-type problems in the real projective plane
• Automated mathematical discovery and verification: minimizing pentagons in the plane
• Erdős-Szekeres maker-breaker games
• Holes in convex and simple drawings
• Erdős-Szekeres maker-breaker games
• Holes in convex and simple drawings

This page was built for publication: On \(k\)-gons and \(k\)-holes in point sets

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