Holes or Empty Pseudo-Triangles in Planar Point Sets

الأصل · EN

Let E(k, ℓ) denote the smallest integer such that any set of at least E(k, ℓ) points in the plane, no three on a line, contains either an empty convex polygon with k vertices or an empty pseudo-triangle with ℓ vertices. The existence of E(k, ℓ) for positive integers k, ℓ≥ 3, 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, ℓ), and prove bounds on E(k, 6) and E(6, ℓ), for k, ℓ≥ 3. By dropping the emptiness condition, we define another related quantity F(k, ℓ), which is the smallest integer such that any set of at least F(k, ℓ) points in the plane, no three on a line, contains a convex polygon with k vertices or a pseudo-triangle with ℓ vertices. Extending a result of Bisztriczky and Tóth [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).