20 Search Results for "Erickson, Jeff"

Document
DOI: 10.4230/LIPIcs.ESA.2024.15
A (5/3+ε)-Approximation for Tricolored Non-Crossing Euclidean TSP

Authors: Júlia Baligács, Yann Disser, Andreas Emil Feldmann, and Anna Zych-Pawlewicz

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
In the Tricolored Euclidean Traveling Salesperson problem, we are given k = 3 sets of points in the plane and are looking for disjoint tours, each covering one of the sets. Arora (1998) famously gave a PTAS based on "patching" for the case k = 1 and, recently, Dross et al. (2023) generalized this result to k = 2. Our contribution is a (5/3+ε)-approximation algorithm for k = 3 that further generalizes Arora’s approach. It is believed that patching is generally no longer possible for more than two tours. We circumvent this issue by either applying a conditional patching scheme for three tours or using an alternative approach based on a weighted solution for k = 2.
Cite as

Júlia Baligács, Yann Disser, Andreas Emil Feldmann, and Anna Zych-Pawlewicz. A (5/3+ε)-Approximation for Tricolored Non-Crossing Euclidean TSP. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 15:1-15:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{baligacs_et_al:LIPIcs.ESA.2024.15,
  author =	{Balig\'{a}cs, J\'{u}lia and Disser, Yann and Feldmann, Andreas Emil and Zych-Pawlewicz, Anna},
  title =	{{A (5/3+\epsilon)-Approximation for Tricolored Non-Crossing Euclidean TSP}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{15:1--15:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.15},
  URN =		{urn:nbn:de:0030-drops-210862},
  doi =		{10.4230/LIPIcs.ESA.2024.15},
  annote =	{Keywords: Approximation Algorithms, geometric Network Optimization, Euclidean TSP, non-crossing Structures}
}
Document
DOI: 10.4230/LIPIcs.ESA.2024.34
Exploring the Approximability Landscape of 3SUM

Authors: Karl Bringmann, Ahmed Ghazy, and Marvin Künnemann

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
Since an increasing number of problems in P have conditional lower bounds against exact algorithms, it is natural to study which of these problems can be efficiently approximated. Often, however, there are many potential ways to formulate an approximate version of a problem. We ask: How sensitive is the (in-)approximability of a problem in P to its precise formulation? To this end, we perform a case study using the popular 3SUM problem. Its many equivalent formulations give rise to a wide range of potential approximate relaxations. Specifically, to obtain an approximate relaxation in our framework, one can choose among the options: (a) 3SUM or Convolution 3SUM, (b) monochromatic or trichromatic, (c) allowing under-approximation, over-approximation, or both, (d) approximate decision or approximate optimization, (e) single output or multiple outputs and (f) implicit or explicit target (given as input). We show general reduction principles between some variants and find that we can classify the remaining problems (over polynomially bounded positive integers) into three regimes: 1) (1+ε)-approximable in near-linear time Õ(n + 1/ε), 2) (1+ε)-approximable in near-quadratic time Õ(n/ε) or Õ(n+1/ε²), or 3) non-approximable, i.e., requiring time n^{2± o(1)} even for any approximation factor. In each of these three regimes, we provide matching upper and conditional lower bounds. To prove our results, we establish two results that may be of independent interest: Over polynomially bounded integers, we show subquadratic equivalence of (min,+)-convolution and polyhedral 3SUM, and we prove equivalence of the Strong 3SUM conjecture and the Strong Convolution 3SUM conjecture.
Cite as

Karl Bringmann, Ahmed Ghazy, and Marvin Künnemann. Exploring the Approximability Landscape of 3SUM. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 34:1-34:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bringmann_et_al:LIPIcs.ESA.2024.34,
  author =	{Bringmann, Karl and Ghazy, Ahmed and K\"{u}nnemann, Marvin},
  title =	{{Exploring the Approximability Landscape of 3SUM}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{34:1--34:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.34},
  URN =		{urn:nbn:de:0030-drops-211057},
  doi =		{10.4230/LIPIcs.ESA.2024.34},
  annote =	{Keywords: Fine-grained Complexity, Conditional Lower Bounds, Approximation Schemes, Min-Plus Convolution}
}
Document
DOI: 10.4230/LIPIcs.ESA.2024.66
Shortest Path Separators in Unit Disk Graphs

Authors: Elfarouk Harb, Zhengcheng Huang, and Da Wei Zheng

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
We introduce a new balanced separator theorem for unit-disk graphs involving two shortest paths combined with the 1-hop neighbours of those paths and two other vertices. This answers an open problem of Yan, Xiang and Dragan [CGTA '12] and improves their result that requires removing the 3-hop neighbourhood of two shortest paths. Our proof uses very different ideas, including Delaunay triangulations and a generalization of the celebrated balanced separator theorem of Lipton and Tarjan [J. Appl. Math. '79] to systems of non-intersecting paths.
Cite as

Elfarouk Harb, Zhengcheng Huang, and Da Wei Zheng. Shortest Path Separators in Unit Disk Graphs. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 66:1-66:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{harb_et_al:LIPIcs.ESA.2024.66,
  author =	{Harb, Elfarouk and Huang, Zhengcheng and Zheng, Da Wei},
  title =	{{Shortest Path Separators in Unit Disk Graphs}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{66:1--66:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.66},
  URN =		{urn:nbn:de:0030-drops-211375},
  doi =		{10.4230/LIPIcs.ESA.2024.66},
  annote =	{Keywords: Balanced shortest path separators, unit disk graphs, crossings}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2024.9
Quantum Algorithms for Hopcroft’s Problem

Authors: Vladimirs Andrejevs, Aleksandrs Belovs, and Jevgēnijs Vihrovs

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract
In this work we study quantum algorithms for Hopcroft’s problem which is a fundamental problem in computational geometry. Given n points and n lines in the plane, the task is to determine whether there is a point-line incidence. The classical complexity of this problem is well-studied, with the best known algorithm running in O(n^{4/3}) time, with matching lower bounds in some restricted settings. Our results are two different quantum algorithms with time complexity Õ(n^{5/6}). The first algorithm is based on partition trees and the quantum backtracking algorithm. The second algorithm uses a quantum walk together with a history-independent dynamic data structure for storing line arrangement which supports efficient point location queries. In the setting where the number of points and lines differ, the quantum walk-based algorithm is asymptotically faster. The quantum speedups for the aforementioned data structures may be useful for other geometric problems.
Cite as

Vladimirs Andrejevs, Aleksandrs Belovs, and Jevgēnijs Vihrovs. Quantum Algorithms for Hopcroft’s Problem. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{andrejevs_et_al:LIPIcs.MFCS.2024.9,
  author =	{Andrejevs, Vladimirs and Belovs, Aleksandrs and Vihrovs, Jevg\={e}nijs},
  title =	{{Quantum Algorithms for Hopcroft’s Problem}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{9:1--9:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.9},
  URN =		{urn:nbn:de:0030-drops-205653},
  doi =		{10.4230/LIPIcs.MFCS.2024.9},
  annote =	{Keywords: Quantum algorithms, Quantum walks, Computational Geometry}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2024.38
Algorithms and Complexity for Path Covers of Temporal DAGs

Authors: Dibyayan Chakraborty, Antoine Dailly, Florent Foucaud, and Ralf Klasing

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract
A path cover of a digraph is a collection of paths collectively containing its vertex set. A path cover with minimum cardinality for a directed acyclic graph can be found in polynomial time [Fulkerson, AMS'56; Cáceres et al., SODA'22]. Moreover, Dilworth’s celebrated theorem on chain coverings of partially ordered sets equivalently states that the minimum size of a path cover of a DAG is equal to the maximum size of a set of mutually unreachable vertices. In this paper, we examine how far these classic results can be extended to a dynamic setting. A temporal digraph has an arc set that changes over discrete time-steps; if the underlying digraph is acyclic, then it is a temporal DAG. A temporal path is a directed path in the underlying digraph, such that the time-steps of arcs are strictly increasing along the path. Two temporal paths are temporally disjoint if they do not occupy any vertex at the same time. A temporal path cover is a collection 𝒞 of temporal paths that covers all vertices, and 𝒞 is temporally disjoint if all its temporal paths are pairwise temporally disjoint. We study the computational complexities of the problems of finding a minimum-size temporal (disjoint) path cover (denoted as Temporal Path Cover and Temporally Disjoint Path Cover). On the negative side, we show that both Temporal Path Cover and Temporally Disjoint Path Cover are NP-hard even when the underlying DAG is planar, bipartite, subcubic, and there are only two arc-disjoint time-steps. Moreover, Temporally Disjoint Path Cover remains NP-hard even on temporal oriented trees. We also observe that natural temporal analogues of Dilworth’s theorem on these classes of temporal DAGs do not hold. In contrast, we show that Temporal Path Cover is polynomial-time solvable on temporal oriented trees by a reduction to Clique Cover for (static undirected) weakly chordal graphs (a subclass of perfect graphs for which Clique Cover admits an efficient algorithm). This highlights an interesting algorithmic difference between the two problems. Although it is NP-hard on temporal oriented trees, Temporally Disjoint Path Cover becomes polynomial-time solvable on temporal oriented lines and temporal rooted directed trees. Motivated by the hardness result on trees, we show that, in contrast, Temporal Path Cover admits an XP time algorithm with respect to parameter t_max + tw, where t_max is the maximum time-step and tw is the treewidth of the underlying static undirected graph; moreover, Temporally Disjoint Path Cover admits an FPT algorithm with respect to the same parameterization.
Cite as

Dibyayan Chakraborty, Antoine Dailly, Florent Foucaud, and Ralf Klasing. Algorithms and Complexity for Path Covers of Temporal DAGs. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 38:1-38:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chakraborty_et_al:LIPIcs.MFCS.2024.38,
  author =	{Chakraborty, Dibyayan and Dailly, Antoine and Foucaud, Florent and Klasing, Ralf},
  title =	{{Algorithms and Complexity for Path Covers of Temporal DAGs}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{38:1--38:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.38},
  URN =		{urn:nbn:de:0030-drops-205940},
  doi =		{10.4230/LIPIcs.MFCS.2024.38},
  annote =	{Keywords: Temporal Graphs, Dilworth’s Theorem, DAGs, Path Cover, Temporally Disjoint Paths, Algorithms, Oriented Trees, Treewidth}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2024.70
On Line-Separable Weighted Unit-Disk Coverage and Related Problems

Authors: Gang Liu and Haitao Wang

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract
Given a set P of n points and a set S of n weighted disks in the plane, the disk coverage problem is to compute a subset of disks of smallest total weight such that the union of the disks in the subset covers all points of P. The problem is NP-hard. In this paper, we consider a line-separable unit-disk version of the problem where all disks have the same radius and their centers are separated from the points of P by a line 𝓁. We present an O(n^{3/2}log² n) time algorithm for the problem. This improves the previously best work of O(n²log n) time. Our result leads to an algorithm of O(n^{7/2}log² n) time for the halfplane coverage problem (i.e., using n weighted halfplanes to cover n points), an improvement over the previous O(n⁴log n) time solution. If all halfplanes are lower ones, our algorithm runs in O(n^{3/2}log² n) time, while the previous best algorithm takes O(n²log n) time. Using duality, the hitting set problems under the same settings can be solved with similar time complexities.
Cite as

Gang Liu and Haitao Wang. On Line-Separable Weighted Unit-Disk Coverage and Related Problems. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 70:1-70:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{liu_et_al:LIPIcs.MFCS.2024.70,
  author =	{Liu, Gang and Wang, Haitao},
  title =	{{On Line-Separable Weighted Unit-Disk Coverage and Related Problems}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{70:1--70:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.70},
  URN =		{urn:nbn:de:0030-drops-206265},
  doi =		{10.4230/LIPIcs.MFCS.2024.70},
  annote =	{Keywords: Line-separable, unit disks, halfplanes, geometric coverage, geometric hitting set}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.95
Fully Dynamic Strongly Connected Components in Planar Digraphs

Authors: Adam Karczmarz and Marcin Smulewicz

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
In this paper we consider maintaining strongly connected components (SCCs) of a directed planar graph subject to edge insertions and deletions. We show a data structure maintaining an implicit representation of the SCCs within Õ(n^{6/7}) worst-case time per update. The data structure supports, in O(log²{n}) time, reporting vertices of any specified SCC (with constant overhead per reported vertex) and aggregating vertex information (e.g., computing the maximum label) over all the vertices of that SCC. Furthermore, it can maintain global information about the structure of SCCs, such as the number of SCCs, or the size of the largest SCC. To the best of our knowledge, no fully dynamic SCCs data structures with sublinear update time have been previously known for any major subclass of digraphs. Our result should be contrasted with the n^{1-o(1)} amortized update time lower bound conditional on SETH, which holds even for dynamically maintaining whether a general digraph has more than two SCCs.
Cite as

Adam Karczmarz and Marcin Smulewicz. Fully Dynamic Strongly Connected Components in Planar Digraphs. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 95:1-95:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{karczmarz_et_al:LIPIcs.ICALP.2024.95,
  author =	{Karczmarz, Adam and Smulewicz, Marcin},
  title =	{{Fully Dynamic Strongly Connected Components in Planar Digraphs}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{95:1--95:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.95},
  URN =		{urn:nbn:de:0030-drops-202388},
  doi =		{10.4230/LIPIcs.ICALP.2024.95},
  annote =	{Keywords: dynamic strongly connected components, dynamic strong connectivity, dynamic reachability, planar graphs}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.ISAAC.2022.2
The Tragedy of Being Almost but Not Quite Planar (Invited Talk)

Authors: Jeff Erickson

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
Planar graphs have been fertile grounds for algorithms research for decades, both because they model several types of real-world networks, and because they admit simpler and and faster algorithms than arbitrary graphs. Many important structural properties of planar graphs extend naturally to graphs that embed on more complex surfaces. As a result, efficient algorithms for planar graphs often extend naturally to higher-genus surface graphs with little or no modification. I will describe a few of my favorite exceptions to this rule - classical problems that admit simple, efficient, and practical algorithms for planar graphs, but where algorithms for graphs on other surfaces are significantly slower and/or more complex.
Cite as

Jeff Erickson. The Tragedy of Being Almost but Not Quite Planar (Invited Talk). In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{erickson:LIPIcs.ISAAC.2022.2,
  author =	{Erickson, Jeff},
  title =	{{The Tragedy of Being Almost but Not Quite Planar}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{2:1--2:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.2},
  URN =		{urn:nbn:de:0030-drops-172875},
  doi =		{10.4230/LIPIcs.ISAAC.2022.2},
  annote =	{Keywords: planar graphs, surface graphs, algorithms, open problems}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2021.5
Chasing Puppies: Mobile Beacon Routing on Closed Curves

Authors: Mikkel Abrahamsen, Jeff Erickson, Irina Kostitsyna, Maarten Löffler, Tillmann Miltzow, Jérôme Urhausen, Jordi Vermeulen, and Giovanni Viglietta

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

Abstract
We solve an open problem posed by Michael Biro at CCCG 2013 that was inspired by his and others’ work on beacon-based routing. Consider a human and a puppy on a simple closed curve in the plane. The human can walk along the curve at bounded speed and change direction as desired. The puppy runs with unbounded speed along the curve as long as the Euclidean straight-line distance to the human is decreasing, so that it is always at a point on the curve where the distance is locally minimal. Assuming that the curve is smooth (with some mild genericity constraints) or a simple polygon, we prove that the human can always catch the puppy in finite time.
Cite as

Mikkel Abrahamsen, Jeff Erickson, Irina Kostitsyna, Maarten Löffler, Tillmann Miltzow, Jérôme Urhausen, Jordi Vermeulen, and Giovanni Viglietta. Chasing Puppies: Mobile Beacon Routing on Closed Curves. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 5:1-5:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{abrahamsen_et_al:LIPIcs.SoCG.2021.5,
  author =	{Abrahamsen, Mikkel and Erickson, Jeff and Kostitsyna, Irina and L\"{o}ffler, Maarten and Miltzow, Tillmann and Urhausen, J\'{e}r\^{o}me and Vermeulen, Jordi and Viglietta, Giovanni},
  title =	{{Chasing Puppies: Mobile Beacon Routing on Closed Curves}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{5:1--5:19},
  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.5},
  URN =		{urn:nbn:de:0030-drops-138046},
  doi =		{10.4230/LIPIcs.SoCG.2021.5},
  annote =	{Keywords: Beacon routing, navigation, generic smooth curves, puppies}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2021.23
Algorithms for Contractibility of Compressed Curves on 3-Manifold Boundaries

Authors: Erin Wolf Chambers, Francis Lazarus, Arnaud de Mesmay, and Salman Parsa

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

Abstract
In this paper we prove that the problem of deciding contractibility of an arbitrary closed curve on the boundary of a 3-manifold is in NP. We emphasize that the manifold and the curve are both inputs to the problem. Moreover, our algorithm also works if the curve is given as a compressed word. Previously, such an algorithm was known for simple (non-compressed) curves, and, in very limited cases, for curves with self-intersections. Furthermore, our algorithm is fixed-parameter tractable in the complexity of the input 3-manifold. As part of our proof, we obtain new polynomial-time algorithms for compressed curves on surfaces, which we believe are of independent interest. We provide a polynomial-time algorithm which, given an orientable surface and a compressed loop on the surface, computes a canonical form for the loop as a compressed word. In particular, contractibility of compressed curves on surfaces can be decided in polynomial time; prior published work considered only constant genus surfaces. More generally, we solve the following normal subgroup membership problem in polynomial time: given an arbitrary orientable surface, a compressed closed curve γ, and a collection of disjoint normal curves Δ, there is a polynomial-time algorithm to decide if γ lies in the normal subgroup generated by components of Δ in the fundamental group of the surface after attaching the curves to a basepoint.
Cite as

Erin Wolf Chambers, Francis Lazarus, Arnaud de Mesmay, and Salman Parsa. Algorithms for Contractibility of Compressed Curves on 3-Manifold Boundaries. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 23:1-23:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{chambers_et_al:LIPIcs.SoCG.2021.23,
  author =	{Chambers, Erin Wolf and Lazarus, Francis and de Mesmay, Arnaud and Parsa, Salman},
  title =	{{Algorithms for Contractibility of Compressed Curves on 3-Manifold Boundaries}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{23:1--23:16},
  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.23},
  URN =		{urn:nbn:de:0030-drops-138223},
  doi =		{10.4230/LIPIcs.SoCG.2021.23},
  annote =	{Keywords: 3-manifolds, surfaces, low-dimensional topology, contractibility, compressed curves}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.12
Homotopic Curve Shortening and the Affine Curve-Shortening Flow

Authors: Sergey Avvakumov and Gabriel Nivasch

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

Abstract
We define and study a discrete process that generalizes the convex-layer decomposition of a planar point set. Our process, which we call homotopic curve shortening (HCS), starts with a closed curve (which might self-intersect) in the presence of a set P⊂ ℝ² of point obstacles, and evolves in discrete steps, where each step consists of (1) taking shortcuts around the obstacles, and (2) reducing the curve to its shortest homotopic equivalent. We find experimentally that, if the initial curve is held fixed and P is chosen to be either a very fine regular grid or a uniformly random point set, then HCS behaves at the limit like the affine curve-shortening flow (ACSF). This connection between HCS and ACSF generalizes the link between "grid peeling" and the ACSF observed by Eppstein et al. (2017), which applied only to convex curves, and which was studied only for regular grids. We prove that HCS satisfies some properties analogous to those of ACSF: HCS is invariant under affine transformations, preserves convexity, and does not increase the total absolute curvature. Furthermore, the number of self-intersections of a curve, or intersections between two curves (appropriately defined), does not increase. Finally, if the initial curve is simple, then the number of inflection points (appropriately defined) does not increase.
Cite as

Sergey Avvakumov and Gabriel Nivasch. Homotopic Curve Shortening and the Affine Curve-Shortening Flow. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 12:1-12:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{avvakumov_et_al:LIPIcs.SoCG.2020.12,
  author =	{Avvakumov, Sergey and Nivasch, Gabriel},
  title =	{{Homotopic Curve Shortening and the Affine Curve-Shortening Flow}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{12:1--12:15},
  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.12},
  URN =		{urn:nbn:de:0030-drops-121708},
  doi =		{10.4230/LIPIcs.SoCG.2020.12},
  annote =	{Keywords: affine curve-shortening flow, shortest homotopic path, integer grid, convex-layer decomposition}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.40
A Toroidal Maxwell-Cremona-Delaunay Correspondence

Authors: Jeff Erickson and Patrick Lin

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

Abstract
We consider three classes of geodesic embeddings of graphs on Euclidean flat tori: - A torus graph G is equilibrium if it is possible to place positive weights on the edges, such that the weighted edge vectors incident to each vertex of G sum to zero. - A torus graph G is reciprocal if there is a geodesic embedding of the dual graph G^* on the same flat torus, where each edge of G is orthogonal to the corresponding dual edge in G^*. - A torus graph G is coherent if it is possible to assign weights to the vertices, so that G is the (intrinsic) weighted Delaunay graph of its vertices. The classical Maxwell-Cremona correspondence and the well-known correspondence between convex hulls and weighted Delaunay triangulations imply that the analogous concepts for plane graphs (with convex outer faces) are equivalent. Indeed, all three conditions are equivalent to G being the projection of the 1-skeleton of the lower convex hull of points in ℝ³. However, this three-way equivalence does not extend directly to geodesic graphs on flat tori. On any flat torus, reciprocal and coherent graphs are equivalent, and every reciprocal graph is equilibrium, but not every equilibrium graph is reciprocal. We establish a weaker correspondence: Every equilibrium graph on any flat torus is affinely equivalent to a reciprocal/coherent graph on some flat torus.
Cite as

Jeff Erickson and Patrick Lin. A Toroidal Maxwell-Cremona-Delaunay Correspondence. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 40:1-40:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{erickson_et_al:LIPIcs.SoCG.2020.40,
  author =	{Erickson, Jeff and Lin, Patrick},
  title =	{{A Toroidal Maxwell-Cremona-Delaunay Correspondence}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{40:1--40:17},
  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.40},
  URN =		{urn:nbn:de:0030-drops-121984},
  doi =		{10.4230/LIPIcs.SoCG.2020.40},
  annote =	{Keywords: combinatorial topology, geometric graphs, homology, flat torus, spring embedding, intrinsic Delaunay}
}
Document
DOI: 10.4230/DagRep.9.4.107
Computational Geometry (Dagstuhl Seminar 19181)

Authors: Siu-Wing Cheng, Anne Driemel, and Jeff Erickson

Published in: Dagstuhl Reports, Volume 9, Issue 4 (2019)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 19181 "Computational Geometry". The seminar was held from April 28 to May 3, 2019 and 40 participants from various countries attended it. New advances and directions in computational geometry were presented and discussed. The report collects the abstracts of talks and open problems presented in the seminar.
Cite as

Siu-Wing Cheng, Anne Driemel, and Jeff Erickson. Computational Geometry (Dagstuhl Seminar 19181). In Dagstuhl Reports, Volume 9, Issue 4, pp. 107-123, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Article{cheng_et_al:DagRep.9.4.107,
  author =	{Cheng, Siu-Wing and Driemel, Anne and Erickson, Jeff},
  title =	{{Computational Geometry (Dagstuhl Seminar 19181)}},
  pages =	{107--123},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2019},
  volume =	{9},
  number =	{4},
  editor =	{Cheng, Siu-Wing and Driemel, Anne and Erickson, Jeff},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.9.4.107},
  URN =		{urn:nbn:de:0030-drops-113064},
  doi =		{10.4230/DagRep.9.4.107},
  annote =	{Keywords: Computational geometry, polynomial partition, geometric data structures, approximation}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2019.25
Lower Bounds for Electrical Reduction on Surfaces

Authors: Hsien-Chih Chang, Marcos Cossarini, and Jeff Erickson

Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)

Abstract
We strengthen the connections between electrical transformations and homotopy from the planar setting - observed and studied since Steinitz - to arbitrary surfaces with punctures. As a result, we improve our earlier lower bound on the number of electrical transformations required to reduce an n-vertex graph on surface in the worst case [SOCG 2016] in two different directions. Our previous Omega(n^{3/2}) lower bound applies only to facial electrical transformations on plane graphs with no terminals. First we provide a stronger Omega(n^2) lower bound when the planar graph has two or more terminals, which follows from a quadratic lower bound on the number of homotopy moves in the annulus. Our second result extends our earlier Omega(n^{3/2}) lower bound to the wider class of planar electrical transformations, which preserve the planarity of the graph but may delete cycles that are not faces of the given embedding. This new lower bound follow from the observation that the defect of the medial graph of a planar graph is the same for all its planar embeddings.
Cite as

Hsien-Chih Chang, Marcos Cossarini, and Jeff Erickson. Lower Bounds for Electrical Reduction on Surfaces. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 25:1-25:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{chang_et_al:LIPIcs.SoCG.2019.25,
  author =	{Chang, Hsien-Chih and Cossarini, Marcos and Erickson, Jeff},
  title =	{{Lower Bounds for Electrical Reduction on Surfaces}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{25:1--25:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Barequet, Gill and Wang, Yusu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.25},
  URN =		{urn:nbn:de:0030-drops-104294},
  doi =		{10.4230/LIPIcs.SoCG.2019.25},
  annote =	{Keywords: electrical transformation, Delta-Y-transformation, homotopy, tight, defect, SPQR-tree, smoothings, routing set, 2-flipping}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2019.34
Topologically Trivial Closed Walks in Directed Surface Graphs

Authors: Jeff Erickson and Yipu Wang

Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)

Abstract
Let G be a directed graph with n vertices and m edges, embedded on a surface S, possibly with boundary, with first Betti number beta. We consider the complexity of finding closed directed walks in G that are either contractible (trivial in homotopy) or bounding (trivial in integer homology) in S. Specifically, we describe algorithms to determine whether G contains a simple contractible cycle in O(n+m) time, or a contractible closed walk in O(n+m) time, or a bounding closed walk in O(beta (n+m)) time. Our algorithms rely on subtle relationships between strong connectivity in G and in the dual graph G^*; our contractible-closed-walk algorithm also relies on a seminal topological result of Hass and Scott. We also prove that detecting simple bounding cycles is NP-hard. We also describe three polynomial-time algorithms to compute shortest contractible closed walks, depending on whether the fundamental group of the surface is free, abelian, or hyperbolic. A key step in our algorithm for hyperbolic surfaces is the construction of a context-free grammar with O(g^2L^2) non-terminals that generates all contractible closed walks of length at most L, and only contractible closed walks, in a system of quads of genus g >= 2. Finally, we show that computing shortest simple contractible cycles, shortest simple bounding cycles, and shortest bounding closed walks are all NP-hard.
Cite as

Jeff Erickson and Yipu Wang. Topologically Trivial Closed Walks in Directed Surface Graphs. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 34:1-34:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{erickson_et_al:LIPIcs.SoCG.2019.34,
  author =	{Erickson, Jeff and Wang, Yipu},
  title =	{{Topologically Trivial Closed Walks in Directed Surface Graphs}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{34:1--34:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Barequet, Gill and Wang, Yusu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.34},
  URN =		{urn:nbn:de:0030-drops-104383},
  doi =		{10.4230/LIPIcs.SoCG.2019.34},
  annote =	{Keywords: computational topology, surface-embedded graphs, homotopy, homology, strong connectivity, hyperbolic geometry, medial axes, context-free grammars}
}
  • Refine by Author
  • 11 Erickson, Jeff
  • 2 Chang, Hsien-Chih
  • 2 Driemel, Anne
  • 1 Abrahamsen, Mikkel
  • 1 Akitaya, Hugo A.
  • Show More...

  • Refine by Classification
  • 8 Theory of computation → Computational geometry
  • 3 Theory of computation → Design and analysis of algorithms
  • 2 Mathematics of computing → Geometric topology
  • 2 Mathematics of computing → Graphs and surfaces
  • 2 Theory of computation → Graph algorithms analysis
  • Show More...

  • Refine by Keyword
  • 4 planar graphs
  • 3 Algorithms
  • 3 approximation
  • 3 homotopy
  • 2 algorithms
  • Show More...

  • Refine by Type
  • 20 document

  • Refine by Publication Year
  • 7 2024
  • 3 2016
  • 3 2019
  • 2 2020
  • 2 2021
  • Show More...

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