Mathematics – Combinatorics
Scientific paper
2010-11-02
Mathematics
Combinatorics
18 pages, 24 figures
Scientific paper
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, \ell\geq 3$, is the consequence of a result proved by Valtr [{\it Discrete and Computational Geometry}, Vol. 37, 565--576, 2007]. In this paper, following a series of new results regarding 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 new bounds on $E(k, 6)$ and $E(6, \ell)$, for $k, \ell\geq 3$. By dropping the emptiness condition from $E(k, \ell)$, we get 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 [{\it 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)$.
Bhattacharya Bhaswar B.
Das Sandip
No associations
LandOfFree
Holes or Empty Pseudo-Triangles in Planar Point Sets does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Holes or Empty Pseudo-Triangles in Planar Point Sets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Holes or Empty Pseudo-Triangles in Planar Point Sets will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-594939