10 Search Results for "Nayyeri, Amir"


Document
Track A: Algorithms, Complexity and Games
Hodge Decomposition and General Laplacian Solvers for Embedded Simplicial Complexes

Authors: Mitchell Black and Amir Nayyeri

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)


Abstract
We describe a nearly-linear time algorithm to solve the linear system L₁x = b parameterized by the first Betti number of the complex, where L₁ is the 1-Laplacian of a simplicial complex K that is a subcomplex of a collapsible complex X linearly embedded in ℝ³. Our algorithm generalizes the work of Black et al. [SODA2022] that solved the same problem but required that K have trivial first homology. Our algorithm works for complexes K with arbitrary first homology with running time that is nearly-linear with respect to the size of the complex and polynomial with respect to the first Betti number. The key to our solver is a new algorithm for computing the Hodge decomposition of 1-chains of K in nearly-linear time. Additionally, our algorithm implies a nearly quadratic solver and nearly quadratic Hodge decomposition for the 1-Laplacian of any simplicial complex K embedded in ℝ³, as K can always be expanded to a collapsible embedded complex of quadratic complexity.

Cite as

Mitchell Black and Amir Nayyeri. Hodge Decomposition and General Laplacian Solvers for Embedded Simplicial Complexes. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 23:1-23:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{black_et_al:LIPIcs.ICALP.2022.23,
  author =	{Black, Mitchell and Nayyeri, Amir},
  title =	{{Hodge Decomposition and General Laplacian Solvers for Embedded Simplicial Complexes}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{23:1--23:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.23},
  URN =		{urn:nbn:de:0030-drops-163641},
  doi =		{10.4230/LIPIcs.ICALP.2022.23},
  annote =	{Keywords: Computational Topology, Laplacian solvers, Combinatorial Laplacian, Hodge decomposition, Parameterized Complexity}
}
Document
On Cyclic Solutions to the Min-Max Latency Multi-Robot Patrolling Problem

Authors: Peyman Afshani, Mark de Berg, Kevin Buchin, Jie Gao, Maarten Löffler, Amir Nayyeri, Benjamin Raichel, Rik Sarkar, Haotian Wang, and Hao-Tsung Yang

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


Abstract
We consider the following surveillance problem: Given a set P of n sites in a metric space and a set R of k robots with the same maximum speed, compute a patrol schedule of minimum latency for the robots. Here a patrol schedule specifies for each robot an infinite sequence of sites to visit (in the given order) and the latency L of a schedule is the maximum latency of any site, where the latency of a site s is the supremum of the lengths of the time intervals between consecutive visits to s. When k = 1 the problem is equivalent to the travelling salesman problem (TSP) and thus it is NP-hard. For k ≥ 2 (which is the version we are interested in) the problem becomes even more challenging; for example, it is not even clear if the decision version of the problem is decidable, in particular in the Euclidean case. We have two main results. We consider cyclic solutions in which the set of sites must be partitioned into 𝓁 groups, for some 𝓁 ≤ k, and each group is assigned a subset of the robots that move along the travelling salesman tour of the group at equal distance from each other. Our first main result is that approximating the optimal latency of the class of cyclic solutions can be reduced to approximating the optimal travelling salesman tour on some input, with only a 1+ε factor loss in the approximation factor and an O((k/ε) ^k) factor loss in the runtime, for any ε > 0. Our second main result shows that an optimal cyclic solution is a 2(1-1/k)-approximation of the overall optimal solution. Note that for k = 2 this implies that an optimal cyclic solution is optimal overall. We conjecture that this is true for k ≥ 3 as well. The results have a number of consequences. For the Euclidean version of the problem, for instance, combining our results with known results on Euclidean TSP, yields a PTAS for approximating an optimal cyclic solution, and it yields a (2(1-1/k)+ε)-approximation of the optimal unrestricted (not necessarily cyclic) solution. If the conjecture mentioned above is true, then our algorithm is actually a PTAS for the general problem in the Euclidean setting. Similar results can be obtained by combining our results with other known TSP algorithms in non-Euclidean metrics.

Cite as

Peyman Afshani, Mark de Berg, Kevin Buchin, Jie Gao, Maarten Löffler, Amir Nayyeri, Benjamin Raichel, Rik Sarkar, Haotian Wang, and Hao-Tsung Yang. On Cyclic Solutions to the Min-Max Latency Multi-Robot Patrolling Problem. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 2:1-2:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{afshani_et_al:LIPIcs.SoCG.2022.2,
  author =	{Afshani, Peyman and de Berg, Mark and Buchin, Kevin and Gao, Jie and L\"{o}ffler, Maarten and Nayyeri, Amir and Raichel, Benjamin and Sarkar, Rik and Wang, Haotian and Yang, Hao-Tsung},
  title =	{{On Cyclic Solutions to the Min-Max Latency Multi-Robot Patrolling Problem}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{2:1--2:14},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.2},
  URN =		{urn:nbn:de:0030-drops-160109},
  doi =		{10.4230/LIPIcs.SoCG.2022.2},
  annote =	{Keywords: Approximation, Motion Planning, Scheduling}
}
Document
ETH-Tight Algorithms for Finding Surfaces in Simplicial Complexes of Bounded Treewidth

Authors: Mitchell Black, Nello Blaser, Amir Nayyeri, and Erlend Raa Vågset

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


Abstract
Given a simplicial complex with n simplices, we consider the Connected Subsurface Recognition (c-SR) problem of finding a subcomplex that is homeomorphic to a given connected surface with a fixed boundary. We also study the related Sum-of-Genus Subsurface Recognition (SoG) problem, where we instead search for a surface whose boundary, number of connected components, and total genus are given. For both of these problems, we give parameterized algorithms with respect to the treewidth k of the Hasse diagram that run in 2^{O(k log k)}n^{O(1)} time. For the SoG problem, we also prove that our algorithm is optimal assuming the exponential-time hypothesis. In fact, we prove the stronger result that our algorithm is ETH-tight even without restriction on the total genus.

Cite as

Mitchell Black, Nello Blaser, Amir Nayyeri, and Erlend Raa Vågset. ETH-Tight Algorithms for Finding Surfaces in Simplicial Complexes of Bounded Treewidth. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 17:1-17:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{black_et_al:LIPIcs.SoCG.2022.17,
  author =	{Black, Mitchell and Blaser, Nello and Nayyeri, Amir and V\r{a}gset, Erlend Raa},
  title =	{{ETH-Tight Algorithms for Finding Surfaces in Simplicial Complexes of Bounded Treewidth}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{17:1--17:16},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.17},
  URN =		{urn:nbn:de:0030-drops-160253},
  doi =		{10.4230/LIPIcs.SoCG.2022.17},
  annote =	{Keywords: Computational Geometry, Surface Recognition, Treewidth, Hasse Diagram, Simplicial Complexes, Low-Dimensional Topology, Parameterized Complexity, Computational Complexity}
}
Document
Effective Resistance and Capacitance in Simplicial Complexes and a Quantum Algorithm

Authors: Mitchell Black and William Maxwell

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)


Abstract
We investigate generalizations of the graph theoretic notions of effective resistance and capacitance to simplicial complexes and prove analogs of formulas known in the case of graphs. In graphs the effective resistance between two vertices is O(n); however, we show that in a simplicial complex the effective resistance of a null-homologous cycle may be exponential. This is caused by relative torsion in the simplicial complex. We provide upper bounds on both effective resistance and capacitance that are polynomial in the number of simplices as well as the maximum cardinality of the torsion subgroup of a relative homology group denoted 𝒯_{max}(𝒦). We generalize the quantum algorithm deciding st-connectivity in a graph and obtain an algorithm deciding whether or not a (d-1)-dimensional cycle γ is null-homologous in a d-dimensional simplicial complex 𝒦. The quantum algorithm has query complexity parameterized by the effective resistance and capacitance of γ. Using our upper bounds we find that the query complexity is O (n^{5/2}⋅ d^{1/2} ⋅ 𝒯_{max}(𝒦)²). Under the assumptions that γ is the boundary of a d-simplex (which may or may not be included in the complex) and that 𝒦 is relative torsion-free, we match the O(n^{3/2}) query complexity obtained for st-connectivity. These assumptions always hold in the case of st-connectivity. We provide an implementation of the algorithm whose running time is polynomial in the size of the complex and the relative torsion. Finally, we prove a duality theorem relating effective resistance and capacitance when 𝒦 is d-dimensional and admits an embedding into ℝ^{d+1}.

Cite as

Mitchell Black and William Maxwell. Effective Resistance and Capacitance in Simplicial Complexes and a Quantum Algorithm. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 31:1-31:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{black_et_al:LIPIcs.ISAAC.2021.31,
  author =	{Black, Mitchell and Maxwell, William},
  title =	{{Effective Resistance and Capacitance in Simplicial Complexes and a Quantum Algorithm}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{31:1--31:27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.31},
  URN =		{urn:nbn:de:0030-drops-154641},
  doi =		{10.4230/LIPIcs.ISAAC.2021.31},
  annote =	{Keywords: Simplicial complexes, quantum computing}
}
Document
Generalized Max-Flows and Min-Cuts in Simplicial Complexes

Authors: William Maxwell and Amir Nayyeri

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)


Abstract
We consider high dimensional variants of the maximum flow and minimum cut problems in the setting of simplicial complexes and provide both algorithmic and hardness results. By viewing flows and cuts topologically in terms of the simplicial (co)boundary operator we can state these problems as linear programs and show that they are dual to one another. Unlike graphs, complexes with integral capacity constraints may have fractional max-flows. We show that computing a maximum integral flow is NP-hard. Moreover, we give a combinatorial definition of a simplicial cut that seems more natural in the context of optimization problems and show that computing such a cut is NP-hard. However, we provide conditions on the simplicial complex for when the cut found by the linear program is a combinatorial cut. For d-dimensional simplicial complexes embedded into ℝ^{d+1} we provide algorithms operating on the dual graph: computing a maximum flow is dual to computing a shortest path and computing a minimum cut is dual to computing a minimum cost circulation. Finally, we investigate the Ford-Fulkerson algorithm on simplicial complexes, prove its correctness, and provide a heuristic which guarantees it to halt.

Cite as

William Maxwell and Amir Nayyeri. Generalized Max-Flows and Min-Cuts in Simplicial Complexes. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 69:1-69:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{maxwell_et_al:LIPIcs.ESA.2021.69,
  author =	{Maxwell, William and Nayyeri, Amir},
  title =	{{Generalized Max-Flows and Min-Cuts in Simplicial Complexes}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{69:1--69:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.69},
  URN =		{urn:nbn:de:0030-drops-146509},
  doi =		{10.4230/LIPIcs.ESA.2021.69},
  annote =	{Keywords: Max-flow min-cut, simplicial complexes, algebraic topology}
}
Document
Low-Stretch Spanning Trees of Graphs with Bounded Width

Authors: Glencora Borradaile, Erin Wolf Chambers, David Eppstein, William Maxwell, and Amir Nayyeri

Published in: LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)


Abstract
We study the problem of low-stretch spanning trees in graphs of bounded width: bandwidth, cutwidth, and treewidth. We show that any simple connected graph G with a linear arrangement of bandwidth b can be embedded into a distribution T of spanning trees such that the expected stretch of each edge of G is O(b²). Our proof implies a linear time algorithm for sampling from T. Therefore, we have a linear time algorithm that finds a spanning tree of G with average stretch O(b²) with high probability. We also describe a deterministic linear-time algorithm for computing a spanning tree of G with average stretch O(b³). For graphs of cutwidth c, we construct a spanning tree with stretch O(c²) in linear time. Finally, when G has treewidth k we provide a dynamic programming algorithm computing a minimum stretch spanning tree of G that runs in polynomial time with respect to the number of vertices of G.

Cite as

Glencora Borradaile, Erin Wolf Chambers, David Eppstein, William Maxwell, and Amir Nayyeri. Low-Stretch Spanning Trees of Graphs with Bounded Width. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 15:1-15:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{borradaile_et_al:LIPIcs.SWAT.2020.15,
  author =	{Borradaile, Glencora and Chambers, Erin Wolf and Eppstein, David and Maxwell, William and Nayyeri, Amir},
  title =	{{Low-Stretch Spanning Trees of Graphs with Bounded Width}},
  booktitle =	{17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
  pages =	{15:1--15:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-150-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{162},
  editor =	{Albers, Susanne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.15},
  URN =		{urn:nbn:de:0030-drops-122622},
  doi =		{10.4230/LIPIcs.SWAT.2020.15},
  annote =	{Keywords: Treewidth, low-stretch spanning tree, fundamental cycle basis}
}
Document
Minimum Bounded Chains and Minimum Homologous Chains in Embedded Simplicial Complexes

Authors: Glencora Borradaile, William Maxwell, and Amir Nayyeri

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


Abstract
We study two optimization problems on simplicial complexes with homology over ℤ₂, the minimum bounded chain problem: given a d-dimensional complex 𝒦 embedded in ℝ^(d+1) and a null-homologous (d-1)-cycle C in 𝒦, find the minimum d-chain with boundary C, and the minimum homologous chain problem: given a (d+1)-manifold ℳ and a d-chain D in ℳ, find the minimum d-chain homologous to D. We show strong hardness results for both problems even for small values of d; d = 2 for the former problem, and d=1 for the latter problem. We show that both problems are APX-hard, and hard to approximate within any constant factor assuming the unique games conjecture. On the positive side, we show that both problems are fixed-parameter tractable with respect to the size of the optimal solution. Moreover, we provide an O(√{log β_d})-approximation algorithm for the minimum bounded chain problem where β_d is the dth Betti number of 𝒦. Finally, we provide an O(√{log n_{d+1}})-approximation algorithm for the minimum homologous chain problem where n_{d+1} is the number of (d+1)-simplices in ℳ.

Cite as

Glencora Borradaile, William Maxwell, and Amir Nayyeri. Minimum Bounded Chains and Minimum Homologous Chains in Embedded Simplicial Complexes. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{borradaile_et_al:LIPIcs.SoCG.2020.21,
  author =	{Borradaile, Glencora and Maxwell, William and Nayyeri, Amir},
  title =	{{Minimum Bounded Chains and Minimum Homologous Chains in Embedded Simplicial Complexes}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{21:1--21: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.21},
  URN =		{urn:nbn:de:0030-drops-121799},
  doi =		{10.4230/LIPIcs.SoCG.2020.21},
  annote =	{Keywords: computational topology, algorithmic complexity, simplicial complexes}
}
Document
All-Pairs Minimum Cuts in Near-Linear Time for Surface-Embedded Graphs

Authors: Glencora Borradaile, David Eppstein, Amir Nayyeri, and Christian Wulff-Nilsen

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


Abstract
For an undirected n-vertex graph G with non-negative edge-weights, we consider the following type of query: given two vertices s and t in G, what is the weight of a minimum st-cut in G? We solve this problem in preprocessing time O(n log^3 n) for graphs of bounded genus, giving the first sub-quadratic time algorithm for this class of graphs. Our result also improves by a logarithmic factor a previous algorithm by Borradaile, Sankowski and Wulff-Nilsen (FOCS 2010) that applied only to planar graphs. Our algorithm constructs a Gomory-Hu tree for the given graph, providing a data structure with space O(n) that can answer minimum-cut queries in constant time. The dependence on the genus of the input graph in our preprocessing time is 2^{O(g^2)}.

Cite as

Glencora Borradaile, David Eppstein, Amir Nayyeri, and Christian Wulff-Nilsen. All-Pairs Minimum Cuts in Near-Linear Time for Surface-Embedded Graphs. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 22:1-22:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{borradaile_et_al:LIPIcs.SoCG.2016.22,
  author =	{Borradaile, Glencora and Eppstein, David and Nayyeri, Amir and Wulff-Nilsen, Christian},
  title =	{{All-Pairs Minimum Cuts in Near-Linear Time for Surface-Embedded Graphs}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{22:1--22: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.22},
  URN =		{urn:nbn:de:0030-drops-59149},
  doi =		{10.4230/LIPIcs.SoCG.2016.22},
  annote =	{Keywords: minimum cuts, surface-embedded graphs, Gomory-Hu tree}
}
Document
Minimum Cycle and Homology Bases of Surface Embedded Graphs

Authors: Glencora Borradaile, Erin Wolf Chambers, Kyle Fox, and Amir Nayyeri

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


Abstract
We study the problems of finding a minimum cycle basis (a minimum weight set of cycles that form a basis for the cycle space) and a minimum homology basis (a minimum weight set of cycles that generates the 1-dimensional (Z_2)-homology classes) of an undirected graph embedded on an orientable surface of genus g. The problems are closely related, because the minimum cycle basis of a graph contains its minimum homology basis, and the minimum homology basis of the 1-skeleton of any graph is exactly its minimum cycle basis. For the minimum cycle basis problem, we give a deterministic O(n^omega + 2^2g n^2)-time algorithm. The best known existing algorithms for surface embedded graphs are those for general sparse graphs: an O(n^omega) time Monte Carlo algorithm [Amaldi et. al., ESA'09] and a deterministic O(n^3) time algorithm [Mehlhorn and Michail, TALG'09]. For the minimum homology basis problem, we give an O(g^3 n log n)-time algorithm, improving on existing algorithms for many values of g and n.

Cite as

Glencora Borradaile, Erin Wolf Chambers, Kyle Fox, and Amir Nayyeri. Minimum Cycle and Homology Bases of Surface Embedded Graphs. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 23:1-23:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{borradaile_et_al:LIPIcs.SoCG.2016.23,
  author =	{Borradaile, Glencora and Chambers, Erin Wolf and Fox, Kyle and Nayyeri, Amir},
  title =	{{Minimum Cycle and Homology Bases of Surface Embedded Graphs}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{23:1--23:15},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.23},
  URN =		{urn:nbn:de:0030-drops-59152},
  doi =		{10.4230/LIPIcs.SoCG.2016.23},
  annote =	{Keywords: Cycle basis, Homology basis, Topological graph theory}
}
Document
On Computing the Fréchet Distance Between Surfaces

Authors: Amir Nayyeri and Hanzhong Xu

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


Abstract
We describe two (1+epsilon)-approximation algorithms for computing the Fréchet distance between two homeomorphic piecewise linear surfaces R and S of genus zero and total complexity n, with Frechet distance delta. (1) A 2^{O((n + ( (Area(R)+Area(S))/(epsilon.delta)^2 )^2 )} time algorithm if R and S are composed of fat triangles (triangles with angles larger than a constant). (2) An O(D/(epsilon.delta)^2) n + 2^{O(D^4/(epsilon^4.delta^2))} time algorithm if R and S are polyhedral terrains over [0,1]^2 with slope at most D. Although, the Fréchet distance between curves has been studied extensively, very little is known for surfaces. Our results are the first algorithms (both for surfaces and terrains) that are guaranteed to terminate in finite time. Our latter result, in particular, implies a linear time algorithm for terrains of constant maximum slope and constant Frechet distance.

Cite as

Amir Nayyeri and Hanzhong Xu. On Computing the Fréchet Distance Between Surfaces. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 55:1-55:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{nayyeri_et_al:LIPIcs.SoCG.2016.55,
  author =	{Nayyeri, Amir and Xu, Hanzhong},
  title =	{{On Computing the Fr\'{e}chet Distance Between Surfaces}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{55:1--55:15},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.55},
  URN =		{urn:nbn:de:0030-drops-59471},
  doi =		{10.4230/LIPIcs.SoCG.2016.55},
  annote =	{Keywords: Surfaces, Terrains, Frechet distance, Parametrized complexity, normal coordinates}
}
  • Refine by Author
  • 9 Nayyeri, Amir
  • 4 Borradaile, Glencora
  • 4 Maxwell, William
  • 3 Black, Mitchell
  • 2 Chambers, Erin Wolf
  • Show More...

  • Refine by Classification
  • 4 Theory of computation → Computational geometry
  • 3 Mathematics of computing → Algebraic topology
  • 3 Theory of computation → Design and analysis of algorithms
  • 1 Mathematics of computing → Graph algorithms
  • 1 Mathematics of computing → Numerical analysis

  • Refine by Keyword
  • 2 Parameterized Complexity
  • 2 Treewidth
  • 2 simplicial complexes
  • 1 Approximation
  • 1 Combinatorial Laplacian
  • Show More...

  • Refine by Type
  • 10 document

  • Refine by Publication Year
  • 3 2016
  • 3 2022
  • 2 2020
  • 2 2021

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