4 Search Results for "Banyassady, Bahareh"


Document
Unlabeled Multi-Robot Motion Planning with Tighter Separation Bounds

Authors: Bahareh Banyassady, Mark de Berg, Karl Bringmann, Kevin Buchin, Henning Fernau, Dan Halperin, Irina Kostitsyna, Yoshio Okamoto, and Stijn Slot

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


Abstract
We consider the unlabeled motion-planning problem of m unit-disc robots moving in a simple polygonal workspace of n edges. The goal is to find a motion plan that moves the robots to a given set of m target positions. For the unlabeled variant, it does not matter which robot reaches which target position as long as all target positions are occupied in the end. If the workspace has narrow passages such that the robots cannot fit through them, then the free configuration space, representing all possible unobstructed positions of the robots, will consist of multiple connected components. Even if in each component of the free space the number of targets matches the number of start positions, the motion-planning problem does not always have a solution when the robots and their targets are positioned very densely. In this paper, we prove tight bounds on how much separation between start and target positions is necessary to always guarantee a solution. Moreover, we describe an algorithm that always finds a solution in time O(n log n + mn + m²) if the separation bounds are met. Specifically, we prove that the following separation is sufficient: any two start positions are at least distance 4 apart, any two target positions are at least distance 4 apart, and any pair of a start and a target positions is at least distance 3 apart. We further show that when the free space consists of a single connected component, the separation between start and target positions is not necessary.

Cite as

Bahareh Banyassady, Mark de Berg, Karl Bringmann, Kevin Buchin, Henning Fernau, Dan Halperin, Irina Kostitsyna, Yoshio Okamoto, and Stijn Slot. Unlabeled Multi-Robot Motion Planning with Tighter Separation Bounds. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 12:1-12:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{banyassady_et_al:LIPIcs.SoCG.2022.12,
  author =	{Banyassady, Bahareh and de Berg, Mark and Bringmann, Karl and Buchin, Kevin and Fernau, Henning and Halperin, Dan and Kostitsyna, Irina and Okamoto, Yoshio and Slot, Stijn},
  title =	{{Unlabeled Multi-Robot Motion Planning with Tighter Separation Bounds}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{12:1--12: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.12},
  URN =		{urn:nbn:de:0030-drops-160203},
  doi =		{10.4230/LIPIcs.SoCG.2022.12},
  annote =	{Keywords: motion planning, computational geometry, simple polygon}
}
Document
Triconnected Planar Graphs of Maximum Degree Five are Subhamiltonian

Authors: Michael Hoffmann and Boris Klemz

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)


Abstract
We show that every triconnected planar graph of maximum degree five is subhamiltonian planar. A graph is subhamiltonian planar if it is a subgraph of a Hamiltonian planar graph or, equivalently, if it admits a 2-page book embedding. In fact, our result is stronger because we only require vertices of a separating triangle to have degree at most five, all other vertices may have arbitrary degree. This degree bound is tight: We describe a family of triconnected planar graphs that are not subhamiltonian planar and where every vertex of a separating triangle has degree at most six. Our results improve earlier work by Heath and by Bauernöppel and, independently, Bekos, Gronemann, and Raftopoulou, who showed that planar graphs of maximum degree three and four, respectively, are subhamiltonian planar. The proof is constructive and yields a quadratic time algorithm to obtain a subhamiltonian plane cycle for a given graph. As one of our main tools, which might be of independent interest, we devise an algorithm that, in a given 3-connected plane graph satisfying the above degree bounds, collapses each maximal separating triangle into a single edge such that the resulting graph is biconnected, contains no separating triangle, and no separation pair whose vertices are adjacent.

Cite as

Michael Hoffmann and Boris Klemz. Triconnected Planar Graphs of Maximum Degree Five are Subhamiltonian. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 58:1-58:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{hoffmann_et_al:LIPIcs.ESA.2019.58,
  author =	{Hoffmann, Michael and Klemz, Boris},
  title =	{{Triconnected Planar Graphs of Maximum Degree Five are Subhamiltonian}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{58:1--58:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola 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.2019.58},
  URN =		{urn:nbn:de:0030-drops-111797},
  doi =		{10.4230/LIPIcs.ESA.2019.58},
  annote =	{Keywords: Graph drawing, book embedding, Hamiltonian graph, planar graph, bounded degree graph, graph augmentation, computational geometry, SPQR decomposition}
}
Document
Routing in Polygonal Domains

Authors: Bahareh Banyassady, Man-Kwun Chiu, Matias Korman, Wolfgang Mulzer, André van Renssen, Marcel Roeloffzen, Paul Seiferth, Yannik Stein, Birgit Vogtenhuber, and Max Willert

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)


Abstract
We consider the problem of routing a data packet through the visibility graph of a polygonal domain P with n vertices and h holes. We may preprocess P to obtain a label and a routing table for each vertex. Then, we must be able to route a data packet between any two vertices p and q of P , where each step must use only the label of the target node q and the routing table of the current node. For any fixed eps > 0, we pre ent a routing scheme that always achieves a routing path that exceeds the shortest path by a factor of at most 1 + eps. The labels have O(log n) bits, and the routing tables are of size O((eps^{-1} + h) log n). The preprocessing time is O(n^2 log n + hn^2 + eps^{-1}hn). It can be improved to O(n 2 + eps^{-1}n) for simple polygons.

Cite as

Bahareh Banyassady, Man-Kwun Chiu, Matias Korman, Wolfgang Mulzer, André van Renssen, Marcel Roeloffzen, Paul Seiferth, Yannik Stein, Birgit Vogtenhuber, and Max Willert. Routing in Polygonal Domains. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 10:1-10:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{banyassady_et_al:LIPIcs.ISAAC.2017.10,
  author =	{Banyassady, Bahareh and Chiu, Man-Kwun and Korman, Matias and Mulzer, Wolfgang and van Renssen, Andr\'{e} and Roeloffzen, Marcel and Seiferth, Paul and Stein, Yannik and Vogtenhuber, Birgit and Willert, Max},
  title =	{{Routing in Polygonal Domains}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{10:1--10:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.10},
  URN =		{urn:nbn:de:0030-drops-82379},
  doi =		{10.4230/LIPIcs.ISAAC.2017.10},
  annote =	{Keywords: polygonal domains, routing scheme, small stretch,Yao graph}
}
Document
Improved Time-Space Trade-Offs for Computing Voronoi Diagrams

Authors: Bahareh Banyassady, Matias Korman, Wolfgang Mulzer, André van Renssen, Marcel Roeloffzen, Paul Seiferth, and Yannik Stein

Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)


Abstract
Let P be a planar n-point set in general position. For k between 1 and n-1, the Voronoi diagram of order k is obtained by subdividing the plane into regions such that points in the same cell have the same set of nearest k neighbors in P. The (nearest point) Voronoi diagram (NVD) and the farthest point Voronoi diagram (FVD) are the particular cases of k=1 and k=n-1, respectively. It is known that the family of all higher-order Voronoi diagrams of order 1 to K for P can be computed in total time O(n K^2 + n log n) using O(K^2(n-K)) space. Also NVD and FVD can be computed in O(n log n) time using O(n) space. For s in {1, ..., n}, an s-workspace algorithm has random access to a read-only array with the sites of P in arbitrary order. Additionally, the algorithm may use O(s) words of Theta(log n) bits each for reading and writing intermediate data. The output can be written only once and cannot be accessed afterwards. We describe a deterministic s-workspace algorithm for computing an NVD and also an FVD for P that runs in O((n^2/s) log s) time. Moreover, we generalize our s-workspace algorithm for computing the family of all higher-order Voronoi diagrams of P up to order K in O(sqrt(s)) in total time O( (n^2 K^6 / s) log^(1+epsilon)(K) (log s / log K)^(O(1)) ) for any fixed epsilon > 0. Previously, for Voronoi diagrams, the only known s-workspace algorithm was to find an NVD for P in expected time O((n^2/s) log s + n log s log^*s). Unlike the previous algorithm, our new method is very simple and does not rely on advanced data structures or random sampling techniques.

Cite as

Bahareh Banyassady, Matias Korman, Wolfgang Mulzer, André van Renssen, Marcel Roeloffzen, Paul Seiferth, and Yannik Stein. Improved Time-Space Trade-Offs for Computing Voronoi Diagrams. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 9:1-9:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{banyassady_et_al:LIPIcs.STACS.2017.9,
  author =	{Banyassady, Bahareh and Korman, Matias and Mulzer, Wolfgang and van Renssen, Andr\'{e} and Roeloffzen, Marcel and Seiferth, Paul and Stein, Yannik},
  title =	{{Improved Time-Space Trade-Offs for Computing Voronoi Diagrams}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{9:1--9:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Vollmer, Heribert and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.9},
  URN =		{urn:nbn:de:0030-drops-70249},
  doi =		{10.4230/LIPIcs.STACS.2017.9},
  annote =	{Keywords: memory-constrained model, Voronoi diagram, time-space trade-off}
}
  • Refine by Author
  • 3 Banyassady, Bahareh
  • 2 Korman, Matias
  • 2 Mulzer, Wolfgang
  • 2 Roeloffzen, Marcel
  • 2 Seiferth, Paul
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Computational geometry
  • 1 Human-centered computing → Graph drawings
  • 1 Mathematics of computing → Graphs and surfaces
  • 1 Mathematics of computing → Paths and connectivity problems

  • Refine by Keyword
  • 2 computational geometry
  • 1 Graph drawing
  • 1 Hamiltonian graph
  • 1 SPQR decomposition
  • 1 Voronoi diagram
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 2 2017
  • 1 2019
  • 1 2022

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