{
  "id": "1208.0053",
  "version": "v3",
  "published": "2012-07-31T23:20:20.000Z",
  "updated": "2014-06-16T18:25:57.000Z",
  "title": "Improved bounds for incidences between points and circles",
  "authors": [
    "Micha Sharir",
    "Adam Sheffer",
    "Joshua Zahl"
  ],
  "categories": [
    "math.CO",
    "cs.CG"
  ],
  "abstract": "We establish an improved upper bound for the number of incidences between m points and n circles in three dimensions. The previous best known bound, originally established for the planar case and later extended to any dimension $\\ge 2$, is $O*(m^{2/3}n^{2/3} + m^{6/11}n^{9/11}+m+n)$, where the $O*(\\cdot)$ notation hides sub-polynomial factors. Since all the points and circles may lie on a common plane (or sphere), it is impossible to improve the bound in R^3 without first improving it in the plane. Nevertheless, we show that if the set of circles is required to be \"truly three-dimensional\" in the sense that no sphere or plane contains more than $q$ of the circles, for some $q << n$, then the bound can be improved to \\[O*(m^{3/7}n^{6/7} + m^{2/3}n^{1/2}q^{1/6} + m^{6/11}n^{15/22}q^{3/22} + m + n). \\] For various ranges of parameters (e.g., when $m=\\Theta(n)$ and $q = o(n^{7/9})$), this bound is smaller than the lower bound $\\Omega*(m^{2/3}n^{2/3}+m+n)$, which holds in two dimensions. We present several extensions and applications of the new bound: (i) For the special case where all the circles have the same radius, we obtain the improved bound $O*(m^{5/11}n^{9/11} + m^{2/3}n^{1/2}q^{1/6} + m + n$. (ii) We present an improved analysis that removes the subpolynomial factors from the bound when $m=O(n^{3/2-\\eps})$ for any fixed $\\varepsilon >0$. (iii) We use our results to obtain the improved bound $O(m^{15/7})$ for the number of mutually similar triangles determined by any set of $m$ points in R^3. Our result is obtained by applying the polynomial partitioning technique of Guth and Katz using a constant-degree partitioning polynomial (as was also recently used by Solymosi and Tao). We also rely on various additional tools from analytic, algebraic, and combinatorial geometry.",
  "revisions": [
    {
      "version": "v3",
      "updated": "2014-06-16T18:25:57.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "incidences",
      "notation hides sub-polynomial factors",
      "planar case",
      "combinatorial geometry",
      "polynomial partitioning technique"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2012arXiv1208.0053S"
    }
  }
}