On k-gons and k-holes in point sets

DOI10.1016/J.COMGEO.2014.12.007zbMATH Open1330.52019DBLPjournals/comgeo/AichholzerMGHHH15arXiv1409.0081OpenAlexW2168172768WikidataQ61732468 ScholiaQ61732468MaRDI QIDQ899713FDOQ899713

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)

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.

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

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

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (15)

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

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)