License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SOCG.2015.553
URN: urn:nbn:de:0030-drops-51107
URL: http://drops.dagstuhl.de/opus/volltexte/2015/5110/
Go to the corresponding LIPIcs Volume Portal


Sharir, Micha ; Solomon, Noam

Incidences between Points and Lines in Three Dimensions

pdf-format:
27.pdf (0.5 MB)


Abstract

We give a fairly elementary and simple proof that shows that the number of incidences between m points and n lines in R^3, so that no plane contains more than s lines, is O(m^{1/2}n^{3/4} + m^{2/3}n^{1/3}s^{1/3} + m + n) (in the precise statement, the constant of proportionality of the first and third terms depends, in a rather weak manner, on the relation between m and n). This bound, originally obtained by Guth and Katz as a major step in their solution of Erdos's distinct distances problem, is also a major new result in incidence geometry, an area that has picked up considerable momentum in the past six years. Its original proof uses fairly involved machinery from algebraic and differential geometry, so it is highly desirable to simplify the proof, in the interest of better understanding the geometric structure of the problem, and providing new tools for tackling similar problems. This has recently been undertaken by Guth. The present paper presents a different and simpler derivation, with better bounds than those in Guth, and without the restrictive assumptions made there. Our result has a potential for applications to other incidence problems in higher dimensions.

BibTeX - Entry

@InProceedings{sharir_et_al:LIPIcs:2015:5110,
  author =	{Micha Sharir and Noam Solomon},
  title =	{{Incidences between Points and Lines in Three Dimensions}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{553--568},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Lars Arge and J{\'a}nos Pach},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5110},
  URN =		{urn:nbn:de:0030-drops-51107},
  doi =		{10.4230/LIPIcs.SOCG.2015.553},
  annote =	{Keywords: Combinatorial Geometry, Algebraic Geometry, Incidences, The Polynomial Method}
}

Keywords: Combinatorial Geometry, Algebraic Geometry, Incidences, The Polynomial Method
Seminar: 31st International Symposium on Computational Geometry (SoCG 2015)
Issue Date: 2015
Date of publication: 11.06.2015


DROPS-Home | Fulltext Search | Imprint Published by LZI