Search Results

Documents authored by Parsa, Salman

Document
DOI: 10.4230/LIPIcs.SoCG.2024.65
On the Parameterized Complexity of Motion Planning for Rectangular Robots

Authors: Iyad Kanj and Salman Parsa

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

Abstract
We study computationally-hard fundamental motion planning problems where the goal is to translate k axis-aligned rectangular robots from their initial positions to their final positions without collision, and with the minimum number of translation moves. Our aim is to understand the interplay between the number of robots and the geometric complexity of the input instance measured by the input size, which is the number of bits needed to encode the coordinates of the rectangles' vertices. We focus on axis-aligned translations, and more generally, translations restricted to a given set of directions, and we study the two settings where the robots move in the free plane, and where they are confined to a bounding box. We also consider two modes of motion: serial and parallel. We obtain fixed-parameter tractable (FPT) algorithms parameterized by k for all the settings under consideration. In the case where the robots move serially (i.e., one in each time step) and axis-aligned, we prove a structural result stating that every problem instance admits an optimal solution in which the moves are along a grid, whose size is a function of k, that can be defined based on the input instance. This structural result implies that the problem is fixed-parameter tractable parameterized by k. We also consider the case in which the robots move in parallel (i.e., multiple robots can move during the same time step), and which falls under the category of Coordinated Motion Planning problems. Our techniques for the axis-aligned motion here differ from those for the case of serial motion. We employ a search tree approach and perform a careful examination of the relative geometric positions of the robots that allow us to reduce the problem to FPT-many Linear Programming instances, thus obtaining an FPT algorithm. Finally, we show that, when the robots move in the free plane, the FPT results for the serial motion case carry over to the case where the translations are restricted to any given set of directions.
Cite as

Iyad Kanj and Salman Parsa. On the Parameterized Complexity of Motion Planning for Rectangular Robots. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 65:1-65:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kanj_et_al:LIPIcs.SoCG.2024.65,
  author =	{Kanj, Iyad and Parsa, Salman},
  title =	{{On the Parameterized Complexity of Motion Planning for Rectangular Robots}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{65:1--65:15},
  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.65},
  URN =		{urn:nbn:de:0030-drops-200108},
  doi =		{10.4230/LIPIcs.SoCG.2024.65},
  annote =	{Keywords: motion planning of rectangular robots, coordinated motion planing of rectangular robots, parameterized complexity}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2022.25
On Complexity of Computing Bottleneck and Lexicographic Optimal Cycles in a Homology Class

Authors: Erin Wolf Chambers, Salman Parsa, and Hannah Schreiber

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

Abstract
Homology features of spaces which appear in applications, for instance 3D meshes, are among the most important topological properties of these objects. Given a non-trivial cycle in a homology class, we consider the problem of computing a representative in that homology class which is optimal. We study two measures of optimality, namely, the lexicographic order of cycles (the lex-optimal cycle) and the bottleneck norm (a bottleneck-optimal cycle). We give a simple algorithm for computing the lex-optimal cycle for a 1-homology class in a closed orientable surface. In contrast to this, our main result is that, in the case of 3-manifolds of size n² in the Euclidean 3-space, the problem of finding a bottleneck optimal cycle cannot be solved more efficiently than solving a system of linear equations with an n × n sparse matrix. From this reduction, we deduce several hardness results. Most notably, we show that for 3-manifolds given as a subset of the 3-space of size n², persistent homology computations are at least as hard as rank computation (for sparse matrices) while ordinary homology computations can be done in O(n² log n) time. This is the first such distinction between these two computations. Moreover, it follows that the same disparity exists between the height persistent homology computation and general sub-level set persistent homology computation for simplicial complexes in the 3-space.
Cite as

Erin Wolf Chambers, Salman Parsa, and Hannah Schreiber. On Complexity of Computing Bottleneck and Lexicographic Optimal Cycles in a Homology Class. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 25:1-25:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{chambers_et_al:LIPIcs.SoCG.2022.25,
  author =	{Chambers, Erin Wolf and Parsa, Salman and Schreiber, Hannah},
  title =	{{On Complexity of Computing Bottleneck and Lexicographic Optimal Cycles in a Homology Class}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{25:1--25:15},
  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.25},
  URN =		{urn:nbn:de:0030-drops-160338},
  doi =		{10.4230/LIPIcs.SoCG.2022.25},
  annote =	{Keywords: computational topology, bottleneck optimal cycles, homology}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2022.55
Minimum Height Drawings of Ordered Trees in Polynomial Time: Homotopy Height of Tree Duals

Authors: Tim Ophelders and Salman Parsa

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

Abstract
We consider drawings of graphs in the plane in which vertices are assigned distinct points in the plane and edges are drawn as simple curves connecting the vertices and such that the edges intersect only at their common endpoints. There is an intuitive quality measure for drawings of a graph that measures the height of a drawing ϕ : G↪ℝ² as follows. For a vertical line 𝓁 in ℝ², let the height of 𝓁 be the cardinality of the set 𝓁 ∩ ϕ(G). The height of a drawing of G is the maximum height over all vertical lines. In this paper, instead of abstract graphs, we fix a drawing and consider plane graphs. In other words, we are looking for a homeomorphism of the plane that minimizes the height of the resulting drawing. This problem is equivalent to the homotopy height problem in the plane, and the homotopic Fréchet distance problem. These problems were recently shown to lie in NP, but no polynomial-time algorithm or NP-hardness proof has been found since their formulation in 2009. We present the first polynomial-time algorithm for drawing trees with optimal height. This corresponds to a polynomial-time algorithm for the homotopy height where the triangulation has only one vertex (that is, a set of loops incident to a single vertex), so that its dual is a tree.
Cite as

Tim Ophelders and Salman Parsa. Minimum Height Drawings of Ordered Trees in Polynomial Time: Homotopy Height of Tree Duals. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 55:1-55:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{ophelders_et_al:LIPIcs.SoCG.2022.55,
  author =	{Ophelders, Tim and Parsa, Salman},
  title =	{{Minimum Height Drawings of Ordered Trees in Polynomial Time: Homotopy Height of Tree Duals}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{55:1--55: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.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.55},
  URN =		{urn:nbn:de:0030-drops-160631},
  doi =		{10.4230/LIPIcs.SoCG.2022.55},
  annote =	{Keywords: Graph drawing, homotopy height}
}
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}
}
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