Search Results

Documents authored by Damásdi, Gábor

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.2024.46
Saturation Results Around the Erdős-Szekeres Problem

Authors: Gábor Damásdi, Zichao Dong, Manfred Scheucher, and Ji Zeng

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

Abstract
In this paper, we consider saturation problems related to the celebrated Erdős-Szekeres convex polygon problem. For each n ≥ 7, we construct a planar point set of size (7/8) ⋅ 2^{n-2} which is saturated for convex n-gons. That is, the set contains no n points in convex position while the addition of any new point creates such a configuration. This demonstrates that the saturation number is smaller than the Ramsey number for the Erdős-Szekeres problem. The proof also shows that the original Erdős-Szekeres construction is indeed saturated. Our construction is based on a similar improvement for the saturation version of the cups-versus-caps theorem. Moreover, we consider the generalization of the cups-versus-caps theorem to monotone paths in ordered hypergraphs. In contrast to the geometric setting, we show that this abstract saturation number is always equal to the corresponding Ramsey number.
Cite as

Gábor Damásdi, Zichao Dong, Manfred Scheucher, and Ji Zeng. Saturation Results Around the Erdős-Szekeres Problem. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 46:1-46:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{damasdi_et_al:LIPIcs.SoCG.2024.46,
  author =	{Dam\'{a}sdi, G\'{a}bor and Dong, Zichao and Scheucher, Manfred and Zeng, Ji},
  title =	{{Saturation Results Around the Erd\H{o}s-Szekeres Problem}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{46:1--46: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.46},
  URN =		{urn:nbn:de:0030-drops-199919},
  doi =		{10.4230/LIPIcs.SoCG.2024.46},
  annote =	{Keywords: Convex polygon, Cups-versus-caps, Monotone path, Saturation problem}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2022.32
Three-Chromatic Geometric Hypergraphs

Authors: Gábor Damásdi and Dömötör Pálvölgyi

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Abstract
We prove that for any planar convex body C there is a positive integer m with the property that any finite point set P in the plane can be three-colored such that there is no translate of C containing at least m points of P, all of the same color. As a part of the proof, we show a strengthening of the Erdős-Sands-Sauer-Woodrow conjecture. Surprisingly, the proof also relies on the two dimensional case of the Illumination conjecture.
Cite as

Gábor Damásdi and Dömötör Pálvölgyi. Three-Chromatic Geometric Hypergraphs. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 32:1-32:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{damasdi_et_al:LIPIcs.SoCG.2022.32,
  author =	{Dam\'{a}sdi, G\'{a}bor and P\'{a}lv\"{o}lgyi, D\"{o}m\"{o}t\"{o}r},
  title =	{{Three-Chromatic Geometric Hypergraphs}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{32:1--32:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.32},
  URN =		{urn:nbn:de:0030-drops-160401},
  doi =		{10.4230/LIPIcs.SoCG.2022.32},
  annote =	{Keywords: Discrete geometry, Geometric hypergraph coloring, Decomposition of multiple coverings}
}
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