{
  "id": "2205.03437",
  "version": "v1",
  "published": "2022-05-06T18:22:22.000Z",
  "updated": "2022-05-06T18:22:22.000Z",
  "title": "Finding Points in Convex Position in Density-Restricted Sets",
  "authors": [
    "Adrian Dumitrescu",
    "Csaba D. Tóth"
  ],
  "comment": "19 pages, 6 figures",
  "categories": [
    "math.CO",
    "cs.CG"
  ],
  "abstract": "For a finite set $A\\subset \\mathbb{R}^d$, let $\\Delta(A)$ denote the spread of $A$, which is the ratio of the maximum pairwise distance to the minimum pairwise distance. For a positive integer $n$, let $\\gamma_d(n)$ denote the largest integer such that any set $A$ of $n$ points in general position in $\\mathbb{R}^d$, satisfying $\\Delta(A) \\leq \\alpha n^{1/d}$ for a fixed $\\alpha>0$, contains at least $\\gamma_d(n)$ points in convex position. About $30$ years ago, Valtr proved that $\\gamma_2(n)=\\Theta(n^{1/3})$. Since then no further results have been obtained in higher dimensions. Here we continue this line of research in three dimensions and prove that $ \\gamma_3(n) =\\Theta(n^{1/2})$. The lower bound implies the following approximation: Given any $n$-element point set $A\\subset \\mathbb{R}^3$ in general position, satisfying $\\Delta(A) \\leq \\alpha n^{1/3}$ for a fixed $\\alpha$, a $\\Omega(n^{-1/6})$-factor approximation of the maximum-size convex subset of points can be computed by a randomized algorithm in $O(n \\log{n})$ expected time.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-05-06T18:22:22.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "convex position",
      "density-restricted sets",
      "finding points",
      "general position",
      "lower bound implies"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 19,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}