Holes or empty pseudo-triangles in planar point sets

MaRDI QIDQ1937360zbMATH OpenFDO

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)

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

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)

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)$.

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

Cited in

(3)

• On the number of pseudo-empty convex pentagons for a planar point set
• scientific article; zbMATH DE number 2068096 (Why is no real title available?)
• 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)