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.35
URN: urn:nbn:de:0030-drops-138343
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13834/
Go to the corresponding LIPIcs Volume Portal

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

On Rich Lenses in Planar Arrangements of Circles and Related Problems

pdf-format:
LIPIcs-SoCG-2021-35.pdf (0.7 MB)

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.

BibTeX - Entry

@InProceedings{ezra_et_al:LIPIcs.SoCG.2021.35,
  author =	{Ezra, Esther and Raz, Orit E. and Sharir, Micha and Zahl, Joshua},
  title =	{{On Rich Lenses in Planar Arrangements of Circles and Related Problems}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{35:1--35:15},
  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/13834},
  URN =		{urn:nbn:de:0030-drops-138343},
  doi =		{10.4230/LIPIcs.SoCG.2021.35},
  annote =	{Keywords: Lenses, Circles, Polynomial partitioning, Incidences}
}

Keywords: Lenses, Circles, 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 Published by LZI