LIPIcs.SoCG.2021.35.pdf
- Filesize: 0.72 MB
- 15 pages
Document
On Rich Lenses in Planar Arrangements of Circles and Related Problems
Authors
Esther Ezra 
,
Orit E. Raz ,
Micha Sharir ,
Joshua Zahl
-
Part of:
Volume:
37th International Symposium on Computational Geometry (SoCG 2021)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Computational Geometry (SoCG) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2021-06-02
File
Document Identifiers
Author Details
Cite As Get 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)
0PDF Downloads
References
-
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.
-
P. Agarwal and J. Pach. Combinatorial Geometry. Wiley Interscience, 1995.
-
B. Aronov and M. Sharir. Cutting circles into pseudo-segments and improved bounds for incidences. Discrete Comput. Geom., 28:475-490, 2002.
-
B. Aronov and M. Sharir. Almost tight bounds for eliminating depth cycles in three dimensions. Discrete Comput. Geom., 59:725-741, 2018.
-
J. Ellenberg, J. Solymosi, and J. Zahl. New bounds on curve tangencies and orthogonalities. Discrete Anal., 18, 2016.
-
L. Guth. Polynomial partitioning for a set of varieties. Math. Proc. Cambridge Philos. Soc., 159:459-469, 2015.
-
L. Guth and N.H. Katz. On the Erdős distinct distances problem in the plane. Ann. of Math., 181:155-190, 2015.
-
A. Marcus and G. Tardos. Intersection reverse sequences and geometric applications,. J. Combin. Theory Ser. A, 113:675-691, 2006.
- 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.
-
M. Sharir and J. Zahl. Cutting algebraic curves into pseudo-segments and applications. J. Combin. Theory Ser. A, 150:1-35, 2017.
-
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.
-
L. Székely. Crossing numbers and hard Erdős problems in discrete geometry. Combin. Probab. Comput., 11:1-10, 1993.
-
E. Szemerédi and W.T. Trotter. Extremal problems in discrete geometry,. Combinatorica, 3:381-392, 1983.