License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2021.56
URN: urn:nbn:de:0030-drops-138551
URL: https://drops.dagstuhl.de/opus/volltexte/2021/13855/
 Go to the corresponding LIPIcs Volume Portal

### On Rich Points and Incidences with Restricted Sets of Lines in 3-Space

 pdf-format:

### Abstract

Let L be a set of n lines in ℝ³ that is contained, when represented as points in the four-dimensional Plücker space of lines in ℝ³, in an irreducible variety T of constant degree which is non-degenerate with respect to L (see below). We show:
(1) If T is two-dimensional, the number of r-rich points (points incident to at least r lines of L) is O(n^{4/3+ε}/r²), for r ⩾ 3 and for any ε > 0, and, if at most n^{1/3} lines of L lie on any common regulus, there are at most O(n^{4/3+ε}) 2-rich points. For r larger than some sufficiently large constant, the number of r-rich points is also O(n/r).
As an application, we deduce (with an ε-loss in the exponent) the bound obtained by Pach and de Zeeuw [J. Pach and F. de Zeeuw, 2017] on the number of distinct distances determined by n points on an irreducible algebraic curve of constant degree in the plane that is not a line nor a circle.
(2) If T is two-dimensional, the number of incidences between L and a set of m points in ℝ³ is O(m+n).
(3) If T is three-dimensional and nonlinear, the number of incidences between L and a set of m points in ℝ³ is O (m^{3/5}n^{3/5} + (m^{11/15}n^{2/5} + m^{1/3}n^{2/3})s^{1/3} + m + n), provided that no plane contains more than s of the points. When s = O(min{n^{3/5}/m^{2/5}, m^{1/2}}), the bound becomes O(m^{3/5}n^{3/5}+m+n).
As an application, we prove that the number of incidences between m points and n lines in ℝ⁴ contained in a quadratic hypersurface (which does not contain a hyperplane) is O(m^{3/5}n^{3/5} + m + n).
The proofs use, in addition to various tools from algebraic geometry, recent bounds on the number of incidences between points and algebraic curves in the plane.

### BibTeX - Entry

```@InProceedings{sharir_et_al:LIPIcs.SoCG.2021.56,
author =	{Sharir, Micha and Solomon, Noam},
title =	{{On Rich Points and Incidences with Restricted Sets of Lines in 3-Space}},
booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
pages =	{56:1--56:14},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-184-9},
ISSN =	{1868-8969},
year =	{2021},
volume =	{189},
editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address =	{Dagstuhl, Germany},
URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/13855},
URN =		{urn:nbn:de:0030-drops-138551},
doi =		{10.4230/LIPIcs.SoCG.2021.56},
annote =	{Keywords: Lines in space, Rich points, Polynomial partitioning, Incidences}
}```

 Keywords: Lines in space, Rich points, Polynomial partitioning, Incidences Collection: 37th International Symposium on Computational Geometry (SoCG 2021) Issue Date: 2021 Date of publication: 02.06.2021

DROPS-Home | Fulltext Search | Imprint | Privacy