Search Results

Documents authored by Ackerman, Eyal

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}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.1
An Almost Optimal Bound on the Number of Intersections of Two Simple Polygons

Authors: Eyal Ackerman, Balázs Keszegh, and Günter Rote

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
What is the maximum number of intersections of the boundaries of a simple m-gon and a simple n-gon, assuming general position? This is a basic question in combinatorial geometry, and the answer is easy if at least one of m and n is even. If both m and n are odd, the best known construction has mn-(m+n)+3 intersections, and it is conjectured that this is the maximum. However, the best known upper bound is only mn-(m + ⌈ n/6 ⌉), for m ≥ n. We prove a new upper bound of mn-(m+n)+C for some constant C, which is optimal apart from the value of C.
Cite as

Eyal Ackerman, Balázs Keszegh, and Günter Rote. An Almost Optimal Bound on the Number of Intersections of Two Simple Polygons. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 1:1-1:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{ackerman_et_al:LIPIcs.SoCG.2020.1,
  author =	{Ackerman, Eyal and Keszegh, Bal\'{a}zs and Rote, G\"{u}nter},
  title =	{{An Almost Optimal Bound on the Number of Intersections of Two Simple Polygons}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{1:1--1:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.1},
  URN =		{urn:nbn:de:0030-drops-121591},
  doi =		{10.4230/LIPIcs.SoCG.2020.1},
  annote =	{Keywords: Simple polygon, Ramsey theory, combinatorial geometry}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2016.5
Coloring Points with Respect to Squares

Authors: Eyal Ackerman, Balázs Keszegh, and Máté Vizer

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract
We consider the problem of 2-coloring geometric hypergraphs. Specifically, we show that there is a constant m such that any finite set S of points in the plane can be 2-colored such that every axis-parallel square that contains at least m points from S contains points of both colors. Our proof is constructive, that is, it provides a polynomial-time algorithm for obtaining such a 2-coloring. By affine transformations this result immediately applies also when considering homothets of a fixed parallelogram.
Cite as

Eyal Ackerman, Balázs Keszegh, and Máté Vizer. Coloring Points with Respect to Squares. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 5:1-5:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{ackerman_et_al:LIPIcs.SoCG.2016.5,
  author =	{Ackerman, Eyal and Keszegh, Bal\'{a}zs and Vizer, M\'{a}t\'{e}},
  title =	{{Coloring Points with Respect to Squares}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{5:1--5:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.5},
  URN =		{urn:nbn:de:0030-drops-58972},
  doi =		{10.4230/LIPIcs.SoCG.2016.5},
  annote =	{Keywords: Geometric hypergraph coloring, Polychromatic coloring, Homothets, Cover-decomposability}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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