Holes or empty pseudo-triangles in planar point sets

zbMATH Open1264.52002arXiv1011.0517MaRDI QIDQ1937360FDOQ1937360

Authors: Bhaswar B. Bhattacharya, Sandip Das 

Publication date: 28 February 2013

Published in: Moscow Journal of Combinatorics and Number Theory (Search for Journal in Brave)

Abstract: Let $E(k,ell)$ denote the smallest integer such that any set of at least $E(k,ell)$ points in the plane, no three on a line, contains either an empty convex polygon with $k$ vertices or an empty pseudo-triangle with $ell$ vertices. The existence of $E(k,ell)$ for positive integers $k,ellgeq3$, is the consequence of a result proved by Valtr [Discrete and Computational Geometry, Vol. 37, 565--576, 2007]. In this paper, following a series of new results about the existence of empty pseudo-triangles in point sets with triangular convex hulls, we determine the exact values of $E(k,5)$ and $E(5,ell)$, and prove bounds on $E(k,6)$ and $E(6,ell)$, for $k,ellgeq3$. By dropping the emptiness condition, we define another related quantity $F(k,ell)$, which is the smallest integer such that any set of at least $F(k,ell)$ points in the plane, no three on a line, contains a convex polygon with $k$ vertices or a pseudo-triangle with $ell$ vertices. Extending a result of Bisztriczky and T'oth [Discrete Geometry, Marcel Dekker, 49--58, 2003], we obtain the exact values of $F(k,5)$ and $F(k,6)$, and obtain non-trivial bounds on $F(k,7)$.

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

Recommendations

• Empty pseudo-triangles in point sets
• scientific article; zbMATH DE number 4024179
• scientific article; zbMATH DE number 881170
• A Minimal Planar Point Set with Specified Disjoint Empty Convex Subsets
• Planar point sets with a small number of empty convex polygons

zbMATH Keywords

discrete geometryconvex hullempty convex polygonspseudo-trianglesRamsey-type resultsErdös-Szekeres theorem

Mathematics Subject Classification ID

Convex sets in (2) dimensions (including convex curves) (52A10) Erd?s problems and related topics of discrete geometry (52C10)

Cited In (3)

• On the number of pseudo-empty convex pentagons for a planar point set
• Title not available (Why is that?)
• Empty pseudo-triangles in point sets

This page was built for publication: Holes or empty pseudo-triangles in planar point sets

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