Search Results

Documents authored by Parada, Irene

Document
DOI: 10.4230/LIPIcs.GD.2024.35
On k-Plane Insertion into Plane Drawings

Authors: Julia Katheder, Philipp Kindermann, Fabian Klute, Irene Parada, and Ignaz Rutter

Published in: LIPIcs, Volume 320, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)

Abstract
We introduce the k-Plane Insertion into Plane drawing (k-PIP) problem: given a plane drawing of a planar graph G and a set F of edges, insert the edges in F into the drawing such that the resulting drawing is k-plane. In this paper, we show that the problem is NP-complete for every k ≥ 1, even when G is biconnected and the set F of edges forms a matching or a path. On the positive side, we present a linear-time algorithm for the case that k = 1 and G is a triangulation.
Cite as

Julia Katheder, Philipp Kindermann, Fabian Klute, Irene Parada, and Ignaz Rutter. On k-Plane Insertion into Plane Drawings. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 35:1-35:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{katheder_et_al:LIPIcs.GD.2024.35,
  author =	{Katheder, Julia and Kindermann, Philipp and Klute, Fabian and Parada, Irene and Rutter, Ignaz},
  title =	{{On k-Plane Insertion into Plane Drawings}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{35:1--35:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-343-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{320},
  editor =	{Felsner, Stefan and Klein, Karsten},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.35},
  URN =		{urn:nbn:de:0030-drops-213190},
  doi =		{10.4230/LIPIcs.GD.2024.35},
  annote =	{Keywords: Graph drawing, edge insertion, k-planarity}
}
Document
DOI: 10.4230/LIPIcs.ESA.2024.70
Dynamic Embeddings of Dynamic Single-Source Upward Planar Graphs

Authors: Ivor van der Hoog, Irene Parada, and Eva Rotenberg

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

Abstract
A directed graph G is upward planar if it admits a planar embedding where each edge is y-monotone. Unlike planarity testing, upward planarity testing is NP-hard except in restricted cases, such as when the graph has the single-source property (i.e., each connected component has one source). In this paper, we present a dynamic data structure for maintaining an upward combinatorial embedding ℰ→(G) of a single-source upward planar graph subject to edge deletions, edge contractions, directed edge insertions across a face, and single-source-preserving vertex splits through specified corners (i.e., the gaps between pairs of consecutive edges that share a vertex and a face). We furthermore support changes to the embedding ℰ→(G) in the form of subgraph flips that mirror or slide the placement of a subgraph that is connected to the rest of the graph via at most two vertices. Updates that are incompatible with the current upward planar embedding are identified and rejected. All update operations are supported as long as the graph remains upward planar. In addition, we support queries that can tell whether two vertices can be connected with a directed edge while the graph remains single-source (we call these uplinkability queries). If a pair of vertices are not uplinkable, we facilitate one-flip-linkable queries: These point to a flip that makes them uplinkable, if any such flip exists. We dynamically maintain a linear-size data structure on G which supports incidence queries between a vertex and a face, and uplinkability queries for vertex pairs. We support all updates and queries in O(log² n) worst-case time.
Cite as

Ivor van der Hoog, Irene Parada, and Eva Rotenberg. Dynamic Embeddings of Dynamic Single-Source Upward Planar Graphs. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 70:1-70:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{vanderhoog_et_al:LIPIcs.ESA.2024.70,
  author =	{van der Hoog, Ivor and Parada, Irene and Rotenberg, Eva},
  title =	{{Dynamic Embeddings of Dynamic Single-Source Upward Planar Graphs}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{70:1--70:18},
  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.70},
  URN =		{urn:nbn:de:0030-drops-211410},
  doi =		{10.4230/LIPIcs.ESA.2024.70},
  annote =	{Keywords: dynamic graphs, data structures, computational geometry, graph drawing, graph algorithms, upward planarity}
}
Document
Media Exposition
DOI: 10.4230/LIPIcs.SoCG.2024.89
Optimal In-Place Compaction of Sliding Cubes (Media Exposition)

Authors: Irina Kostitsyna, Tim Ophelders, Irene Parada, Tom Peters, Willem Sonke, and Bettina Speckmann

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

Abstract
The sliding cubes model is a well-established theoretical framework that supports the analysis of reconfiguration algorithms for modular robots consisting of face-connected cubes. This note accompanies a video that explains our in-place algorithm for reconfiguration in the sliding cubes model. Specifically, our algorithm [Irina Kostitsyna et al., 2023] reconfigures any n-cube configuration into a compact canonical shape using a number of moves proportional to the sum of coordinates of the input cubes. As is common in the literature, we can then reconfigure between two arbitrary shapes via their canonical configurations. The number of moves performed by our algorithm is asymptotically worst-case optimal and strictly improves upon the current state-of-the-art.
Cite as

Irina Kostitsyna, Tim Ophelders, Irene Parada, Tom Peters, Willem Sonke, and Bettina Speckmann. Optimal In-Place Compaction of Sliding Cubes (Media Exposition). In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 89:1-89:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kostitsyna_et_al:LIPIcs.SoCG.2024.89,
  author =	{Kostitsyna, Irina and Ophelders, Tim and Parada, Irene and Peters, Tom and Sonke, Willem and Speckmann, Bettina},
  title =	{{Optimal In-Place Compaction of Sliding Cubes}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{89:1--89:4},
  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.89},
  URN =		{urn:nbn:de:0030-drops-200347},
  doi =		{10.4230/LIPIcs.SoCG.2024.89},
  annote =	{Keywords: Sliding cubes, Reconfiguration algorithm, Modular robots}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2024.31
Optimal In-Place Compaction of Sliding Cubes

Authors: Irina Kostitsyna, Tim Ophelders, Irene Parada, Tom Peters, Willem Sonke, and Bettina Speckmann

Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)

Abstract
The sliding cubes model is a well-established theoretical framework that supports the analysis of reconfiguration algorithms for modular robots consisting of face-connected cubes. As is common in the literature, we focus on reconfiguration via an intermediate canonical shape. Specifically, we present an in-place algorithm that reconfigures any n-cube configuration into a compact canonical shape using a number of moves proportional to the sum of coordinates of the input cubes. This result is asymptotically optimal and strictly improves on all prior work. Furthermore, our algorithm directly extends to dimensions higher than three.
Cite as

Irina Kostitsyna, Tim Ophelders, Irene Parada, Tom Peters, Willem Sonke, and Bettina Speckmann. Optimal In-Place Compaction of Sliding Cubes. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 31:1-31:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kostitsyna_et_al:LIPIcs.SWAT.2024.31,
  author =	{Kostitsyna, Irina and Ophelders, Tim and Parada, Irene and Peters, Tom and Sonke, Willem and Speckmann, Bettina},
  title =	{{Optimal In-Place Compaction of Sliding Cubes}},
  booktitle =	{19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)},
  pages =	{31:1--31:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-318-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{294},
  editor =	{Bodlaender, Hans L.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.31},
  URN =		{urn:nbn:de:0030-drops-200713},
  doi =		{10.4230/LIPIcs.SWAT.2024.31},
  annote =	{Keywords: Sliding cubes, Reconfiguration algorithm, Modular robots}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2022.4
Compacting Squares: Input-Sensitive In-Place Reconfiguration of Sliding Squares

Authors: Hugo A. Akitaya, Erik D. Demaine, Matias Korman, Irina Kostitsyna, Irene Parada, Willem Sonke, Bettina Speckmann, Ryuhei Uehara, and Jules Wulms

Published in: LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)

Abstract
Edge-connected configurations of square modules, which can reconfigure through so-called sliding moves, are a well-established theoretical model for modular robots in two dimensions. Dumitrescu and Pach [Graphs and Combinatorics, 2006] proved that it is always possible to reconfigure one edge-connected configuration of n squares into any other using at most O(n²) sliding moves, while keeping the configuration connected at all times. For certain pairs of configurations, reconfiguration may require Ω(n²) sliding moves. However, significantly fewer moves may be sufficient. We prove that it is NP-hard to minimize the number of sliding moves for a given pair of edge-connected configurations. On the positive side we present Gather&Compact, an input-sensitive in-place algorithm that requires only O( ̄P n) sliding moves to transform one configuration into the other, where ̄P is the maximum perimeter of the two bounding boxes. The squares move within the bounding boxes only, with the exception of at most one square at a time which may move through the positions adjacent to the bounding boxes. The O( ̄P n) bound never exceeds O(n²), and is optimal (up to constant factors) among all bounds parameterized by just n and ̄P. Our algorithm is built on the basic principle that well-connected components of modular robots can be transformed efficiently. Hence we iteratively increase the connectivity within a configuration, to finally arrive at a single solid xy-monotone component. We implemented Gather&Compact and compared it experimentally to the in-place modification by Moreno and Sacristán [EuroCG 2020] of the Dumitrescu and Pach algorithm (MSDP). Our experiments show that Gather&Compact consistently outperforms MSDP by a significant margin, on all types of square configurations.
Cite as

Hugo A. Akitaya, Erik D. Demaine, Matias Korman, Irina Kostitsyna, Irene Parada, Willem Sonke, Bettina Speckmann, Ryuhei Uehara, and Jules Wulms. Compacting Squares: Input-Sensitive In-Place Reconfiguration of Sliding Squares. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 4:1-4:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{a.akitaya_et_al:LIPIcs.SWAT.2022.4,
  author =	{A. Akitaya, Hugo and Demaine, Erik D. and Korman, Matias and Kostitsyna, Irina and Parada, Irene and Sonke, Willem and Speckmann, Bettina and Uehara, Ryuhei and Wulms, Jules},
  title =	{{Compacting Squares: Input-Sensitive In-Place Reconfiguration of Sliding Squares}},
  booktitle =	{18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
  pages =	{4:1--4:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-236-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{227},
  editor =	{Czumaj, Artur and Xin, Qin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.4},
  URN =		{urn:nbn:de:0030-drops-161644},
  doi =		{10.4230/LIPIcs.SWAT.2022.4},
  annote =	{Keywords: Sliding cubes, Reconfiguration, Modular robots, NP-hardness}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.72
Crossing-Optimal Extension of Simple Drawings

Authors: Robert Ganian, Thekla Hamm, Fabian Klute, Irene Parada, and Birgit Vogtenhuber

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
In extension problems of partial graph drawings one is given an incomplete drawing of an input graph G and is asked to complete the drawing while maintaining certain properties. A prominent area where such problems arise is that of crossing minimization. For plane drawings and various relaxations of these, there is a number of tractability as well as lower-bound results exploring the computational complexity of crossing-sensitive drawing extension problems. In contrast, comparatively few results are known on extension problems for the fundamental and broad class of simple drawings, that is, drawings in which each pair of edges intersects in at most one point. In fact, the extension problem of simple drawings has only recently been shown to be NP-hard even for inserting a single edge. In this paper we present tractability results for the crossing-sensitive extension problem of simple drawings. In particular, we show that the problem of inserting edges into a simple drawing is fixed-parameter tractable when parameterized by the number of edges to insert and an upper bound on newly created crossings. Using the same proof techniques, we are also able to answer several closely related variants of this problem, among others the extension problem for k-plane drawings. Moreover, using a different approach, we provide a single-exponential fixed-parameter algorithm for the case in which we are only trying to insert a single edge into the drawing.
Cite as

Robert Ganian, Thekla Hamm, Fabian Klute, Irene Parada, and Birgit Vogtenhuber. Crossing-Optimal Extension of Simple Drawings. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 72:1-72:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{ganian_et_al:LIPIcs.ICALP.2021.72,
  author =	{Ganian, Robert and Hamm, Thekla and Klute, Fabian and Parada, Irene and Vogtenhuber, Birgit},
  title =	{{Crossing-Optimal Extension of Simple Drawings}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{72:1--72:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.72},
  URN =		{urn:nbn:de:0030-drops-141412},
  doi =		{10.4230/LIPIcs.ICALP.2021.72},
  annote =	{Keywords: Simple drawings, Extension problems, Crossing minimization, FPT-algorithms}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2021.10
Characterizing Universal Reconfigurability of Modular Pivoting Robots

Authors: Hugo A. Akitaya, Erik D. Demaine, Andrei Gonczi, Dylan H. Hendrickson, Adam Hesterberg, Matias Korman, Oliver Korten, Jayson Lynch, Irene Parada, and Vera Sacristán

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

Abstract
We give both efficient algorithms and hardness results for reconfiguring between two connected configurations of modules in the hexagonal grid. The reconfiguration moves that we consider are "pivots", where a hexagonal module rotates around a vertex shared with another module. Following prior work on modular robots, we define two natural sets of hexagon pivoting moves of increasing power: restricted and monkey moves. When we allow both moves, we present the first universal reconfiguration algorithm, which transforms between any two connected configurations using O(n³) monkey moves. This result strongly contrasts the analogous problem for squares, where there are rigid examples that do not have a single pivoting move preserving connectivity. On the other hand, if we only allow restricted moves, we prove that the reconfiguration problem becomes PSPACE-complete. Moreover, we show that, in contrast to hexagons, the reconfiguration problem for pivoting squares is PSPACE-complete regardless of the set of pivoting moves allowed. In the process, we strengthen the reduction framework of Demaine et al. [FUN'18] that we consider of independent interest.
Cite as

Hugo A. Akitaya, Erik D. Demaine, Andrei Gonczi, Dylan H. Hendrickson, Adam Hesterberg, Matias Korman, Oliver Korten, Jayson Lynch, Irene Parada, and Vera Sacristán. Characterizing Universal Reconfigurability of Modular Pivoting Robots. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 10:1-10:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{a.akitaya_et_al:LIPIcs.SoCG.2021.10,
  author =	{A. Akitaya, Hugo and Demaine, Erik D. and Gonczi, Andrei and Hendrickson, Dylan H. and Hesterberg, Adam and Korman, Matias and Korten, Oliver and Lynch, Jayson and Parada, Irene and Sacrist\'{a}n, Vera},
  title =	{{Characterizing Universal Reconfigurability of Modular Pivoting Robots}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{10:1--10:20},
  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.10},
  URN =		{urn:nbn:de:0030-drops-138094},
  doi =		{10.4230/LIPIcs.SoCG.2021.10},
  annote =	{Keywords: reconfiguration, geometric algorithm, PSPACE-hardness, pivoting hexagons, pivoting squares, modular robots}
}
Document
Media Exposition
DOI: 10.4230/LIPIcs.SoCG.2020.78
Hiding Sliding Cubes: Why Reconfiguring Modular Robots Is Not Easy (Media Exposition)

Authors: Tillmann Miltzow, Irene Parada, Willem Sonke, Bettina Speckmann, and Jules Wulms

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

Abstract
Face-connected configurations of cubes are a common model for modular robots in three dimensions. In this abstract and the accompanying video we study reconfigurations of such modular robots using so-called sliding moves. Using sliding moves, it is always possible to reconfigure one face-connected configuration of n cubes into any other, while keeping the robot connected at all stages of the reconfiguration. For certain configurations Ω(n²) sliding moves are necessary. In contrast, the best current upper bound is O(n³). It has been conjectured that there is always a cube on the outside of any face-connected configuration of cubes which can be moved without breaking connectivity. The existence of such a cube would immediately imply a straight-forward O(n²) reconfiguration algorithm. However, we present a configuration of cubes such that no cube on the outside can move without breaking connectivity. In other words, we show that this particular avenue towards an O(n²) reconfiguration algorithm for face-connected cubes is blocked.
Cite as

Tillmann Miltzow, Irene Parada, Willem Sonke, Bettina Speckmann, and Jules Wulms. Hiding Sliding Cubes: Why Reconfiguring Modular Robots Is Not Easy (Media Exposition). In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 78:1-78:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{miltzow_et_al:LIPIcs.SoCG.2020.78,
  author =	{Miltzow, Tillmann and Parada, Irene and Sonke, Willem and Speckmann, Bettina and Wulms, Jules},
  title =	{{Hiding Sliding Cubes: Why Reconfiguring Modular Robots Is Not Easy}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{78:1--78:5},
  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.78},
  URN =		{urn:nbn:de:0030-drops-122363},
  doi =		{10.4230/LIPIcs.SoCG.2020.78},
  annote =	{Keywords: Sliding cubes, Reconfiguration, Modular robots}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.3
Universal Reconfiguration of Facet-Connected Modular Robots by Pivots: The O(1) Musketeers

Authors: Hugo A. Akitaya, Esther M. Arkin, Mirela Damian, Erik D. Demaine, Vida Dujmović, Robin Flatland, Matias Korman, Belen Palop, Irene Parada, André van Renssen, and Vera Sacristán

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

Abstract
We present the first universal reconfiguration algorithm for transforming a modular robot between any two facet-connected square-grid configurations using pivot moves. More precisely, we show that five extra "helper" modules ("musketeers") suffice to reconfigure the remaining n modules between any two given configurations. Our algorithm uses O(n^2) pivot moves, which is worst-case optimal. Previous reconfiguration algorithms either require less restrictive "sliding" moves, do not preserve facet-connectivity, or for the setting we consider, could only handle a small subset of configurations defined by a local forbidden pattern. Configurations with the forbidden pattern do have disconnected reconfiguration graphs (discrete configuration spaces), and indeed we show that they can have an exponential number of connected components. But forbidding the local pattern throughout the configuration is far from necessary, as we show that just a constant number of added modules (placed to be freely reconfigurable) suffice for universal reconfigurability. We also classify three different models of natural pivot moves that preserve facet-connectivity, and show separations between these models.
Cite as

Hugo A. Akitaya, Esther M. Arkin, Mirela Damian, Erik D. Demaine, Vida Dujmović, Robin Flatland, Matias Korman, Belen Palop, Irene Parada, André van Renssen, and Vera Sacristán. Universal Reconfiguration of Facet-Connected Modular Robots by Pivots: The O(1) Musketeers. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 3:1-3:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{akitaya_et_al:LIPIcs.ESA.2019.3,
  author =	{Akitaya, Hugo A. and Arkin, Esther M. and Damian, Mirela and Demaine, Erik D. and Dujmovi\'{c}, Vida and Flatland, Robin and Korman, Matias and Palop, Belen and Parada, Irene and van Renssen, Andr\'{e} and Sacrist\'{a}n, Vera},
  title =	{{Universal Reconfiguration of Facet-Connected Modular Robots by Pivots: The O(1) Musketeers}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{3:1--3: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.3},
  URN =		{urn:nbn:de:0030-drops-111247},
  doi =		{10.4230/LIPIcs.ESA.2019.3},
  annote =	{Keywords: Reconfiguration, geometric algorithm, pivoting squares, modular robots}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2017.8
A Superlinear Lower Bound on the Number of 5-Holes

Authors: Oswin Aichholzer, Martin Balko, Thomas Hackl, Jan Kyncl, Irene Parada, Manfred Scheucher, Pavel Valtr, and Birgit Vogtenhuber

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract
Let P be a finite set of points in the plane in general position, that is, no three points of P are on a common line. We say that a set H of five points from P is a 5-hole in P if H is the vertex set of a convex 5-gon containing no other points of P. For a positive integer n, let h_5(n) be the minimum number of 5-holes among all sets of n points in the plane in general position. Despite many efforts in the last 30 years, the best known asymptotic lower and upper bounds for h_5(n) have been of order Omega(n) and O(n^2), respectively. We show that h_5(n) = Omega(n(log n)^(4/5)), obtaining the first superlinear lower bound on h_5(n). The following structural result, which might be of independent interest, is a crucial step in the proof of this lower bound. If a finite set P of points in the plane in general position is partitioned by a line l into two subsets, each of size at least 5 and not in convex position, then l intersects the convex hull of some 5-hole in P. The proof of this result is computer-assisted.
Cite as

Oswin Aichholzer, Martin Balko, Thomas Hackl, Jan Kyncl, Irene Parada, Manfred Scheucher, Pavel Valtr, and Birgit Vogtenhuber. A Superlinear Lower Bound on the Number of 5-Holes. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 8:1-8:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{aichholzer_et_al:LIPIcs.SoCG.2017.8,
  author =	{Aichholzer, Oswin and Balko, Martin and Hackl, Thomas and Kyncl, Jan and Parada, Irene and Scheucher, Manfred and Valtr, Pavel and Vogtenhuber, Birgit},
  title =	{{A Superlinear Lower Bound on the Number of 5-Holes}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{8:1--8:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.8},
  URN =		{urn:nbn:de:0030-drops-72008},
  doi =		{10.4230/LIPIcs.SoCG.2017.8},
  annote =	{Keywords: Erd\"{o}s-Szekeres type problem, k-hole, empty k-gon, empty pentagon, planar point set}
}
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