• DocumentCode
    3710116
  • Title

    Incidences between Points and Lines in R^4

  • Author

    Micha Sharir;Noam Solomon

  • Author_Institution
    Sch. of Comput. Sci., Tel Aviv Univ., Tel Aviv, Israel
  • fYear
    2015
  • Firstpage
    1378
  • Lastpage
    1394
  • Abstract
    We show that the number of incidences between m distinct points and n distinct lines in R4 is O(2c√log m(m2/5n4/5 + m) + m1/2n1/2q1/4 + m2/3n1/3s1/3 + n), for a suitable absolute constant c, provided that no 2-plane contains more than s input lines, and no hyperplane or quadric contains more than q lines. The bound holds without the extra factor 2c√log m when m ≤ n6/7 or m ≥ n5/3. Except for this possible factor, the bound is tight in the worst case. The context of this work is incidence geometry, a topic that has been widely studied for more than three decades, with strong connections to a variety of topics, from range searching in computational geometry to the Kakeya problem in harmonic analysis and geometric measure theory. The area has picked up considerable momentum in the past seven years, following the seminal works of Guth and Katz [12, 13], where the later work solves the point-line incidence problem in three dimensions, using new tools and techniques from algebraic geometry. This work extends their result to four dimensions. In doing so, it had to overcome many new technical hurdles that arise from the higher-dimensional context, by developing and adapting more advanced tools from algebraic geometry.
  • Keywords
    "Polynomials","Computational geometry","Computer science","Context","Search problems","Upper bound"
  • Publisher
    ieee
  • Conference_Titel
    Foundations of Computer Science (FOCS), 2015 IEEE 56th Annual Symposium on
  • ISSN
    0272-5428
  • Type

    conf

  • DOI
    10.1109/FOCS.2015.88
  • Filename
    7354462