DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2025.2

The Maximum Number of Digons Formed by Pairwise Intersecting Pseudocircles

Authors: Eyal Ackerman, Gábor Damásdi, Balázs Keszegh, Rom Pinchasi, and Rebeka Raffay

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract

In 1972, Branko Grünbaum conjectured that any nontrivial arrangement of n > 2 pairwise intersecting pseudocircles in the plane can have at most 2n-2 digons (regions enclosed by exactly two pseudoarcs), with the bound being tight. While this conjecture has been confirmed for cylindrical arrangements of pseudocircles and more recently for geometric circles, we extend these results to any simple arrangement of pairwise intersecting pseudocircles.

Cite as

Eyal Ackerman, Gábor Damásdi, Balázs Keszegh, Rom Pinchasi, and Rebeka Raffay. The Maximum Number of Digons Formed by Pairwise Intersecting Pseudocircles. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 2:1-2:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ackerman_et_al:LIPIcs.SoCG.2025.2,
  author =	{Ackerman, Eyal and Dam\'{a}sdi, G\'{a}bor and Keszegh, Bal\'{a}zs and Pinchasi, Rom and Raffay, Rebeka},
  title =	{{The Maximum Number of Digons Formed by Pairwise Intersecting Pseudocircles}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{2:1--2:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.2},
  URN =		{urn:nbn:de:0030-drops-231548},
  doi =		{10.4230/LIPIcs.SoCG.2025.2},
  annote =	{Keywords: pairwise intersecting arrangement, arrangement of pseudocircles, counting digons, tangencies, Gr\"{u}nbaum’s conjecture}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2024.3

On the Number of Digons in Arrangements of Pairwise Intersecting Circles

Authors: Eyal Ackerman, Gábor Damásdi, Balázs Keszegh, Rom Pinchasi, and Rebeka Raffay

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract

A long-standing open conjecture of Branko Grünbaum from 1972 states that any arrangement of n pairwise intersecting pseudocircles in the plane can have at most 2n-2 digons. Agarwal et al. proved this conjecture for arrangements in which there is a common point surrounded by all pseudocircles. Recently, Felsner, Roch and Scheucher showed that Grünbaum’s conjecture is true for arrangements of pseudocircles in which there are three pseudocircles every pair of which creates a digon. In this paper we prove this over 50-year-old conjecture of Grünbaum for any arrangement of pairwise intersecting circles in the plane.

Cite as

Eyal Ackerman, Gábor Damásdi, Balázs Keszegh, Rom Pinchasi, and Rebeka Raffay. On the Number of Digons in Arrangements of Pairwise Intersecting Circles. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 3:1-3:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{ackerman_et_al:LIPIcs.SoCG.2024.3,
  author =	{Ackerman, Eyal and Dam\'{a}sdi, G\'{a}bor and Keszegh, Bal\'{a}zs and Pinchasi, Rom and Raffay, Rebeka},
  title =	{{On the Number of Digons in Arrangements of Pairwise Intersecting Circles}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{3:1--3:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.3},
  URN =		{urn:nbn:de:0030-drops-199480},
  doi =		{10.4230/LIPIcs.SoCG.2024.3},
  annote =	{Keywords: Arrangement of pseudocircles, Counting touchings, Counting digons, Gr\"{u}nbaum’s conjecture}
}

Search Results

Documents authored by Pinchasi, Rom

The Maximum Number of Digons Formed by Pairwise Intersecting Pseudocircles

Abstract

Cite as

On the Number of Digons in Arrangements of Pairwise Intersecting Circles

Abstract

Cite as

Thanks for your feedback!

Could not send message