{
  "id": "2412.14287",
  "version": "v1",
  "published": "2024-12-18T19:30:27.000Z",
  "updated": "2024-12-18T19:30:27.000Z",
  "title": "Subset Selection Problems in Planar Point Sets",
  "authors": [
    "József Balogh",
    "Felix Christian Clemen",
    "Adrian Dumitrescu",
    "Dingyuan Liu"
  ],
  "comment": "19 pages, 4 figures, comments are welcome",
  "categories": [
    "math.CO",
    "cs.CG"
  ],
  "abstract": "Given a finite set satisfying condition $\\mathcal{A}$, the subset selection problem asks, how large of a subset satisfying condition $\\mathcal{B}$ can we find? We make progress on three instances of subset selection problems in planar point sets. Let $n,s\\in\\mathbb{N}$ with $n\\geq s$, and let $P\\subseteq\\mathbb{R}^2$ be a set of $n$ points, where at most $s$ points lie on the same line. Firstly, we select a general position subset of $P$, i.e., a subset containing no $3$ points on the same line. This problem was proposed by Erd\\H{o}s under the regime when $s$ is a constant. For $s$ being non-constant, we give new lower and upper bounds on the maximum size of such a subset. In particular, we show that in the worst case such a set can have size at most $O(n/s)$ when $n^{1/3}\\leq s\\leq n$ and $O(n^{5/6+o(1)}/\\sqrt{s})$ when $3\\leq s\\leq n^{1/3}$. Secondly, we select a monotone general position subset of $P$, that is, a subset in general position where the points are ordered from left to right and their $y$-coordinates are either non-decreasing or non-increasing. We present bounds on the maximum size of such a subset. In particular, when $s=\\Theta(\\sqrt{n})$, our upper and lower bounds differ only by a logarithmic factor. Lastly, we select a subset of $P$ with pairwise distinct slopes. This problem was initially studied by Erd\\H{o}s, Graham, Ruzsa, and Taylor on the grid. We show that for $s=O(\\sqrt{n})$ such a subset of size $\\Omega((n/\\log{s})^{1/3})$ can always be found in $P$. When $s=\\Theta(\\sqrt{n})$, this matches a lower bound given by Zhang on the grid. As for the upper bound, we show that in the worst case such a subset has size at most $O(\\sqrt{n})$ for $2\\leq s\\leq n^{3/8}$ and $O((n/s)^{4/5})$ for $n^{3/8}\\leq s=O(\\sqrt{n})$. The proofs use a wide range of tools such as incidence geometry, probabilistic methods, the hypergraph container method, and additive combinatorics.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-12-18T19:30:27.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "planar point sets",
      "monotone general position subset",
      "worst case",
      "subset selection problem asks",
      "upper bound"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 19,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}