DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2024.28

Computing Shortest Closed Curves on Non-Orientable Surfaces

Authors: Denys Bulavka, Éric Colin de Verdière, and Niloufar Fuladi

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

Abstract

We initiate the study of computing shortest non-separating simple closed curves with some given topological properties on non-orientable surfaces. While, for orientable surfaces, any two non-separating simple closed curves are related by a self-homeomorphism of the surface, and computing shortest such curves has been vastly studied, for non-orientable ones the classification of non-separating simple closed curves up to ambient homeomorphism is subtler, depending on whether the curve is one-sided or two-sided, and whether it is orienting or not (whether it cuts the surface into an orientable one). We prove that computing a shortest orienting (weakly) simple closed curve on a non-orientable combinatorial surface is NP-hard but fixed-parameter tractable in the genus of the surface. In contrast, we can compute a shortest non-separating non-orienting (weakly) simple closed curve with given sidedness in g^{O(1)} ⋅ n log n time, where g is the genus and n the size of the surface. For these algorithms, we develop tools that can be of independent interest, to compute a variation on canonical systems of loops for non-orientable surfaces based on the computation of an orienting curve, and some covering spaces that are essentially quotients of homology covers.

Cite as

Denys Bulavka, Éric Colin de Verdière, and Niloufar Fuladi. Computing Shortest Closed Curves on Non-Orientable Surfaces. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 28:1-28:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bulavka_et_al:LIPIcs.SoCG.2024.28,
  author =	{Bulavka, Denys and Colin de Verdi\`{e}re, \'{E}ric and Fuladi, Niloufar},
  title =	{{Computing Shortest Closed Curves on Non-Orientable Surfaces}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{28:1--28:16},
  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.28},
  URN =		{urn:nbn:de:0030-drops-199731},
  doi =		{10.4230/LIPIcs.SoCG.2024.28},
  annote =	{Keywords: Surface, Graph, Algorithm, Non-orientable surface}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2021.19

Optimal Bounds for the Colorful Fractional Helly Theorem

Authors: Denys Bulavka, Afshin Goodarzi, and Martin Tancer

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

Abstract

The well known fractional Helly theorem and colorful Helly theorem can be merged into the so called colorful fractional Helly theorem. It states: for every α ∈ (0, 1] and every non-negative integer d, there is β_{col} = β_{col}(α, d) ∈ (0, 1] with the following property. Let ℱ₁, … , ℱ_{d+1} be finite nonempty families of convex sets in ℝ^d of sizes n₁, … , n_{d+1}, respectively. If at least α n₁ n₂ ⋯ n_{d+1} of the colorful (d+1)-tuples have a nonempty intersection, then there is i ∈ [d+1] such that ℱ_i contains a subfamily of size at least β_{col} n_i with a nonempty intersection. (A colorful (d+1)-tuple is a (d+1)-tuple (F₁, … , F_{d+1}) such that F_i belongs to ℱ_i for every i.) The colorful fractional Helly theorem was first stated and proved by Bárány, Fodor, Montejano, Oliveros, and Pór in 2014 with β_{col} = α/(d+1). In 2017 Kim proved the theorem with better function β_{col}, which in particular tends to 1 when α tends to 1. Kim also conjectured what is the optimal bound for β_{col}(α, d) and provided the upper bound example for the optimal bound. The conjectured bound coincides with the optimal bounds for the (non-colorful) fractional Helly theorem proved independently by Eckhoff and Kalai around 1984. We verify Kim’s conjecture by extending Kalai’s approach to the colorful scenario. Moreover, we obtain optimal bounds also in a more general setting when we allow several sets of the same color.

Cite as

Denys Bulavka, Afshin Goodarzi, and Martin Tancer. Optimal Bounds for the Colorful Fractional Helly Theorem. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 19:1-19:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bulavka_et_al:LIPIcs.SoCG.2021.19,
  author =	{Bulavka, Denys and Goodarzi, Afshin and Tancer, Martin},
  title =	{{Optimal Bounds for the Colorful Fractional Helly Theorem}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{19:1--19:14},
  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/entities/document/10.4230/LIPIcs.SoCG.2021.19},
  URN =		{urn:nbn:de:0030-drops-138186},
  doi =		{10.4230/LIPIcs.SoCG.2021.19},
  annote =	{Keywords: colorful fractional Helly theorem, d-collapsible, exterior algebra, d-representable}
}

Search Results

Documents authored by Bulavka, Denys

Computing Shortest Closed Curves on Non-Orientable Surfaces

Abstract

Cite as

Optimal Bounds for the Colorful Fractional Helly Theorem

Abstract

Cite as

Thanks for your feedback!

Could not send message