Document Open Access Logo

On Rich Lenses in Planar Arrangements of Circles and Related Problems

Authors Esther Ezra , Orit E. Raz , Micha Sharir , Joshua Zahl

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2021.35.pdf
  • Filesize: 0.72 MB
  • 15 pages

Document Identifiers

Author Details

Esther Ezra
  • School of Computer Science, Bar Ilan University, Ramat Gan, Israel
Orit E. Raz
  • Institute of Mathematics, Hebrew University, Jerusalem, Israel
Micha Sharir
  • School of Computer Science, Tel Aviv University, Israel
Joshua Zahl
  • Department of Mathematics, University of British Columbia, Vancouver, Canada

Funding

  • Ezra, Esther: Work partially supported by NSF CAREER under grant CCF:AF-1553354 and by Grant 824/17 from the Israel Science Foundation.
  • 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.
  • Zahl, Joshua: Work supported by an NSERC Discovery Grant.

Cite AsGet BibTex

Esther Ezra, Orit E. Raz, Micha Sharir, and Joshua Zahl. On Rich Lenses in Planar Arrangements of Circles and Related Problems. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 35:1-35:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.SoCG.2021.35

Abstract

We show that the maximum number of pairwise non-overlapping k-rich lenses (lenses formed by at least k circles) in an arrangement of n circles in the plane is O(n^{3/2}log(n / k^3) k^{-5/2} + n/k), and the sum of the degrees of the lenses of such a family (where the degree of a lens is the number of circles that form it) is O(n^{3/2}log(n/k^3) k^{-3/2} + n). Two independent proofs of these bounds are given, each interesting in its own right (so we believe). We then show that these bounds lead to the known bound of Agarwal et al. (JACM 2004) and Marcus and Tardos (JCTA 2006) on the number of point-circle incidences in the plane. Extensions to families of more general algebraic curves and some other related problems are also considered.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • Lenses
  • Circles
  • 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. P. Agarwal and J. Pach. Combinatorial Geometry. Wiley Interscience, 1995. Google Scholar
  3. B. Aronov and M. Sharir. Cutting circles into pseudo-segments and improved bounds for incidences. Discrete Comput. Geom., 28:475-490, 2002. Google Scholar
  4. B. Aronov and M. Sharir. Almost tight bounds for eliminating depth cycles in three dimensions. Discrete Comput. Geom., 59:725-741, 2018. Google Scholar
  5. J. Ellenberg, J. Solymosi, and J. Zahl. New bounds on curve tangencies and orthogonalities. Discrete Anal., 18, 2016. Google Scholar
  6. L. Guth. Polynomial partitioning for a set of varieties. Math. Proc. Cambridge Philos. Soc., 159:459-469, 2015. Google Scholar
  7. L. Guth and N.H. Katz. On the Erdős distinct distances problem in the plane. Ann. of Math., 181:155-190, 2015. Google Scholar
  8. A. Marcus and G. Tardos. Intersection reverse sequences and geometric applications,. J. Combin. Theory Ser. A, 113:675-691, 2006. Google Scholar
  9. M. Sharir, N. Solomon, and O. Zlydenko. Incidences with curves with almost two degrees of freedom. arXiv e-prints, 2020. URL: http://arxiv.org/abs/2003.02190v2.
  10. M. Sharir and J. Zahl. Cutting algebraic curves into pseudo-segments and applications. J. Combin. Theory Ser. A, 150:1-35, 2017. Google Scholar
  11. M. Sharir and O. Zlydenko. Incidences between points and curves with almost two degrees of freedom. In 36th International Symposium on Computational Geometry (SoCG 2020), volume 164, pages 66:1-66:14, 2020. Google Scholar
  12. L. Székely. Crossing numbers and hard Erdős problems in discrete geometry. Combin. Probab. Comput., 11:1-10, 1993. Google Scholar
  13. E. Szemerédi and W.T. Trotter. Extremal problems in discrete geometry,. Combinatorica, 3:381-392, 1983. Google Scholar
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 Imprint Privacy Contact