{
  "id": "1404.0419",
  "version": "v1",
  "published": "2014-04-01T23:54:45.000Z",
  "updated": "2014-04-01T23:54:45.000Z",
  "title": "Double-normal pairs in space",
  "authors": [
    "János Pach",
    "Konrad Swanepoel"
  ],
  "comment": "15 pages, 1 figure",
  "categories": [
    "math.MG",
    "math.CO"
  ],
  "abstract": "A double-normal pair of a finite set $S$ of points from $R^d$ is a pair of points $\\{p,q\\}$ from $S$ such that $S$ lies in the closed strip bounded by the hyperplanes through $p$ and $q$ perpendicular to $pq$. A double-normal pair $pq$ is strict if $S\\setminus\\{p,q\\}$ lies in the open strip. The problem of estimating the maximum number $N_d(n)$ of double-normal pairs in a set of $n$ points in $R^d$, was initiated by Martini and Soltan (2006). It was shown in a companion paper that in the plane, this maximum is $3\\lfloor n/2\\rfloor$, for every $n>2$. For $d\\geq 3$, it follows from the Erd\\H{o}s-Stone theorem in extremal graph theory that $N_d(n)=\\frac12(1-1/k)n^2 + o(n^2)$ for a suitable positive integer $k=k(d)$. Here we prove that $k(3)=2$ and, in general, $\\lceil d/2\\rceil \\leq k(d)\\leq d-1$. Moreover, asymptotically we have $\\lim_{n\\rightarrow\\infty}k(d)/d=1$. The same bounds hold for the maximum number of strict double-normal pairs.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-04-01T23:54:45.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "52C10"
    ],
    "keywords": [
      "maximum number",
      "strict double-normal pairs",
      "extremal graph theory",
      "finite set",
      "open strip"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 15,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1404.0419P"
    }
  }
}