Document Open Access Logo

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

Authors Micha Sharir , Noam Solomon

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2021.56.pdf
  • Filesize: 0.72 MB
  • 14 pages

Document Identifiers

Author Details

Micha Sharir
  • School of Computer Science, Tel Aviv University, Israel
Noam Solomon
  • School of Computer Science, Tel Aviv University, Israel

Funding

  • Sharir, Micha: Work partially supported by ISF Grant 260/18, by grant 1367/2016 from the German-Israeli Science Foundation (GIF), and by Blavatnik Research Fund in Computer Science at Tel Aviv University.

Acknowledgements

We deeply thank Larry Guth for helpful interaction on this work.

Cite As Get BibTex

Micha Sharir and Noam Solomon. On Rich Points and Incidences with Restricted Sets of Lines in 3-Space. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 56:1-56:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.SoCG.2021.56

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • Lines in space
  • Rich points
  • Polynomial partitioning
  • Incidences

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. P. Agarwal, E. Nevo, J. Pach, R. Pinchasi, M. Sharir, and S. Smorodinsky. Lenses in arrangements of pseudocircles and their applications. J. ACM, 51:139-186, 2004. Google Scholar
  2. B. Aronov and M. Sharir. Cutting circles into pseudo-segments and improved bounds for incidences. Discrete Comput. Geom., 28:475-490, 2002. Google Scholar
  3. J. Cardinal, M. Payne, and N. Solomon. Ramsey-type theorems for lines in 3-space. Discrete Math. Theoret. Comput. Sci., 18, 2016. Google Scholar
  4. K. Clarkson, H. Edelsbrunner, L. Guibas, M. Sharir, and E. Welzl. Combinatorial complexity bounds for arrangements of curves and spheres. Discrete Comput. Geom., 5:99-160, 1990. Google Scholar
  5. G. Elekes, H. Kaplan, and M. Sharir. On lines, joints, and incidences in three dimensions. J. Combinat. Theory, Ser. A, 118:962-977, 2011. Also in URL: https://arxiv.org/abs/0905.1583.
  6. Gy. Elekes and M. Sharir. Incidences in three dimensions and distinct distances in the plane. Combinat. Probab. Comput., 20:571-608, 2011. Also in URL: https://arxiv.org/abs/1005.0982.
  7. D. Fuchs and S. Tabachnikov. Mathematical Omnibus: Thirty Lectures on Classic Mathematics. Amer. Math. Soc. Press, Providence, RI, 2007. Google Scholar
  8. W. Fulton. Introduction to Intersection Theory in Algebraic Geometry. Expository Lectures from the CBMS Regional Conference Held at George Mason University, June 27-July 1, 1983, Vol. 54. AMS Bookstore, 1984. Google Scholar
  9. P. Griffiths and J. Harris. Principles of Algebraic Geometry, volume 52. John Wiley & Sons, New York, 2011. Google Scholar
  10. L. Guth. Polynomial partitioning for a set of varieties. Math. Proc. Cambridge Phil. Soc., 159:459-469, 2015. Also in URL: https://arxiv.org/abs/1410.8871.
  11. L. Guth and N.~H. Katz. On the ErdH os distinct distances problem in the plane. Annals Math., 181:155-190, 2015. Also in URL: https://arxiv.org/abs/1011.4105.
  12. L. Guth and J. Zahl. Algebraic curves, rich points, and doubly-ruled surfaces. Amer. J. Math., 140:1187-1229, 2018. Also in URL: https://arxiv.org/abs/1503.02173.
  13. J. Harris. Algebraic Geometry: A First Course, volume 133. Springer-Verlag, New York, 1992. Google Scholar
  14. H. Kaplan, M. Sharir, and E. Shustin. On lines and joints. Discrete Comput. Geom., 44:838-843, 2010. Also in URL: https://arxiv.org/abs/0906.0558.
  15. A. Marcus and G. Tardos. Intersection reverse sequences and geometric applications. J. Combinat. Theory, Ser. A, 113:675-691, 2006. Google Scholar
  16. J. Pach and F. de Zeeuw. Distinct distances on algebraic curves in the plane. Combinat. Probab. Comput., 26:99-117, 2017. Google Scholar
  17. J. Pach and M. Sharir. On the number of incidences between points and curves. Combinat. Probab. Comput., 7:121-127, 1998. Google Scholar
  18. M. Rudnev. On the number of incidences between points and planes in three dimensions. Combinatorica, 38:219-254, 2018. Google Scholar
  19. M. Sharir, A. Sheffer, and N. Solomon. Incidences with curves in R^d. Electronic J. Combinat., 23(4), 2016. Also in Proc. European Sympos. Algorithms (2015), Springer LNCS 9294, pp. 977-988, and in URL: https://arxiv.org/abs/1512.08267.
  20. M. Sharir, A. Sheffer, and J. Zahl. Improved bounds for incidences between points and circles. Combinat. Probab. Comput., 24:490-520, 2015. Also in URL: https://arxiv.org/abs/1208.0053.
  21. M. Sharir and N. Solomon. On rich points and incidences with restricted sets of lines in 3-space. URL: http://arxiv.org/abs/2012.11913.
  22. M. Sharir and N. Solomon. Incidences between points and lines in R⁴. Discrete Comput. Geom., 57(3):702-756, 2017. Also in Proc. 56th IEEE Sympos. Foundations of Computer Science 2015, 1378-1394, and in URL: https://arxiv.org/abs/1411.0777.
  23. M. Sharir and N. Solomon. Incidences between points and lines on two- and three- dimensional varieties. Discrete Comput. Geom., 59:88-130, 2018. Also in URL: https://arxiv.org/abs/1609.09026.
  24. M. Sharir, N. Solomon, and O. Zlydenko. Incidences with curves with almost two degrees of freedom. https://arxiv.org/abs/2003.02190. Also in Proc. 36th Sympos. on Computational Geometry (2020), 66:1-66:14.
  25. M. Sharir and J. Zahl. Cutting algebraic curves into pseudo-segments and applications. J. Combinat. Theory Ser. A, 150:1-35, 2017. Google Scholar
  26. N. Solomon and R. Zhang. Highly incidental patterns on a quadratic hypersurface in R⁴. Discrete Math., 340:585-590, 2017. Google Scholar
  27. L. Székely. Crossing numbers and hard ErdH os problems in discrete geometry. Combinat. Probab. Comput., 6:353-358, 1997. Google Scholar
  28. E. Szemerédi and W.T. Trotter. Extremal problems in discrete geometry. Combinatorica, 3:381-392, 1983. Google Scholar
  29. J. Zahl. Breaking the 3/2 barrier for unit distances in three dimensions, 2017. URL: http://arxiv.org/abs/1706.05118.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact