{
  "id": "1011.0517",
  "version": "v3",
  "published": "2010-11-02T05:52:05.000Z",
  "updated": "2012-10-17T09:23:30.000Z",
  "title": "Holes or Empty Pseudo-Triangles in Planar Point Sets",
  "authors": [
    "Bhaswar B. Bhattacharya",
    "Sandip Das"
  ],
  "comment": "A minor error in the proof of Theorem 2 fixed. Typos corrected. 19 pages, 11 figures",
  "journal": "Moscow Journal of Combinatorics and Number Theory, 16-46, Vol. 2 (1), 2012",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "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, \\ell\\geq 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, \\ell)$, and prove bounds on $E(k, 6)$ and $E(6, \\ell)$, for $k, \\ell\\geq 3$. 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)$.",
  "revisions": [
    {
      "version": "v3",
      "updated": "2012-10-17T09:23:30.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "52C10",
      "52A10"
    ],
    "keywords": [
      "planar point sets",
      "empty pseudo-triangle",
      "smallest integer",
      "exact values",
      "triangular convex hulls"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 19,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2010arXiv1011.0517B"
    }
  }
}