Document

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

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.

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

Media Exposition

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

We describe SquareSlider, a software framework for visualizing reconfiguration algorithms of modular robots in the sliding square model. In this model, a robot consists of a configuration of squares in a rectangular grid, which can reconfigure through a fixed set of possible moves. SquareSlider is a web-based tool that implements an easy-to-use interface allowing the user to build a configuration, run a reconfiguration algorithm on it, and examine the results.

Willem Sonke and Jules Wulms. An Interactive Framework for Reconfiguration in the Sliding Square Model (Media Exposition). In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 70:1-70:4, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{sonke_et_al:LIPIcs.SoCG.2022.70, author = {Sonke, Willem and Wulms, Jules}, title = {{An Interactive Framework for Reconfiguration in the Sliding Square Model}}, booktitle = {38th International Symposium on Computational Geometry (SoCG 2022)}, pages = {70:1--70:4}, 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.70}, URN = {urn:nbn:de:0030-drops-160781}, doi = {10.4230/LIPIcs.SoCG.2022.70}, annote = {Keywords: Modular robots, Implementation, Visualization} }

Document

**Published in:** LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Given two shapes A and B in the plane with Hausdorff distance 1, is there a shape S with Hausdorff distance 1/2 to and from A and B? The answer is always yes, and depending on convexity of A and/or B, S may be convex, connected, or disconnected. We show a generalization of this result on Hausdorff distances and middle shapes, and show some related properties. We also show that a generalization of such middle shapes implies a morph with a bounded rate of change. Finally, we explore a generalization of the concept of a Hausdorff middle to more than two sets and show how to approximate or compute it.

Marc van Kreveld, Tillmann Miltzow, Tim Ophelders, Willem Sonke, and Jordi L. Vermeulen. Between Shapes, Using the Hausdorff Distance. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 13:1-13:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{vankreveld_et_al:LIPIcs.ISAAC.2020.13, author = {van Kreveld, Marc and Miltzow, Tillmann and Ophelders, Tim and Sonke, Willem and Vermeulen, Jordi L.}, title = {{Between Shapes, Using the Hausdorff Distance}}, booktitle = {31st International Symposium on Algorithms and Computation (ISAAC 2020)}, pages = {13:1--13:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-173-3}, ISSN = {1868-8969}, year = {2020}, volume = {181}, editor = {Cao, Yixin and Cheng, Siu-Wing and Li, Minming}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.13}, URN = {urn:nbn:de:0030-drops-133572}, doi = {10.4230/LIPIcs.ISAAC.2020.13}, annote = {Keywords: computational geometry, Hausdorff distance, shape interpolation} }

Document

**Published in:** LIPIcs, Volume 177, 11th International Conference on Geographic Information Science (GIScience 2021) - Part I (2020)

Outlines (closed loops) delineate areas of interest on terrains, such as regions with a heightened risk of landslides. For various analysis tasks it is necessary to define and compute a volume of earth (soil) based on such an outline, capturing, for example, the possible volume of a landslide in a high-risk region. In this paper we discuss several options to define meaningful 2D surfaces induced by a 1D outline, which allow us to compute such volumes. We experimentally compare the proposed surface options for two applications: similarity of paths on terrains and landslide susceptibility analysis.

Marc van Kreveld, Tim Ophelders, Willem Sonke, Bettina Speckmann, and Kevin Verbeek. Volume from Outlines on Terrains. In 11th International Conference on Geographic Information Science (GIScience 2021) - Part I. Leibniz International Proceedings in Informatics (LIPIcs), Volume 177, pp. 16:1-16:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{vankreveld_et_al:LIPIcs.GIScience.2021.I.16, author = {van Kreveld, Marc and Ophelders, Tim and Sonke, Willem and Speckmann, Bettina and Verbeek, Kevin}, title = {{Volume from Outlines on Terrains}}, booktitle = {11th International Conference on Geographic Information Science (GIScience 2021) - Part I}, pages = {16:1--16:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-166-5}, ISSN = {1868-8969}, year = {2020}, volume = {177}, editor = {Janowicz, Krzysztof and Verstegen, Judith A.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GIScience.2021.I.16}, URN = {urn:nbn:de:0030-drops-130512}, doi = {10.4230/LIPIcs.GIScience.2021.I.16}, annote = {Keywords: Terrain model, similarity, volume, computation} }

Document

Media Exposition

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

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.

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

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

Drainage networks on terrains have been studied extensively from an algorithmic perspective. However, in drainage networks water flow cannot bifurcate and hence they do not model braided rivers (multiple channels which split and join, separated by sediment bars). We initiate the algorithmic study of braided rivers by employing the descending quasi Morse-Smale complex on the river bed (a polyhedral terrain), and extending it with a certain ordering of bars from the one river bank to the other. This allows us to compute a graph that models a representative channel network, consisting of lowest paths. To ensure that channels in this network are sufficiently different we define a sand function that represents the volume of sediment separating them. We show that in general the problem of computing a maximum network of non-crossing channels which are delta-different from each other (as measured by the sand function) is NP-hard. However, using our ordering between the river banks, we can compute a maximum delta-different network that respects this order in polynomial time. We implemented our approach and applied it to simulated and real-world braided rivers.

Maarten Kleinhans, Marc van Kreveld, Tim Ophelders, Willem Sonke, Bettina Speckmann, and Kevin Verbeek. Computing Representative Networks for Braided Rivers. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 48:1-48:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{kleinhans_et_al:LIPIcs.SoCG.2017.48, author = {Kleinhans, Maarten and van Kreveld, Marc and Ophelders, Tim and Sonke, Willem and Speckmann, Bettina and Verbeek, Kevin}, title = {{Computing Representative Networks for Braided Rivers}}, booktitle = {33rd International Symposium on Computational Geometry (SoCG 2017)}, pages = {48:1--48: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.48}, URN = {urn:nbn:de:0030-drops-72204}, doi = {10.4230/LIPIcs.SoCG.2017.48}, annote = {Keywords: braided rivers, Morse-Smale complex, persistence, network extraction, polyhedral terrain} }

Document

Multimedia Contribution

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

Ruler of the Plane is a set of games illustrating concepts from combinatorial and computational geometry. The games are based on the art gallery problem, ham-sandwich cuts, the Voronoi game, and geometric network connectivity problems like the Euclidean minimum spanning tree and traveling salesperson problem.

Sander Beekhuis, Kevin Buchin, Thom Castermans, Thom Hurks, and Willem Sonke. Ruler of the Plane - Games of Geometry (Multimedia Contribution). In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 63:1-63:5, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{beekhuis_et_al:LIPIcs.SoCG.2017.63, author = {Beekhuis, Sander and Buchin, Kevin and Castermans, Thom and Hurks, Thom and Sonke, Willem}, title = {{Ruler of the Plane - Games of Geometry}}, booktitle = {33rd International Symposium on Computational Geometry (SoCG 2017)}, pages = {63:1--63:5}, 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.63}, URN = {urn:nbn:de:0030-drops-72400}, doi = {10.4230/LIPIcs.SoCG.2017.63}, annote = {Keywords: art gallery problem, ham-sandwich cuts, Voronoi game, traveling sales-person problem} }

Document

**Published in:** LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

We show how to represent a simple polygon P by a (pixel-based) grid polygon Q that is simple and whose Hausdorff or Fréchet distance to P is small. For any simple polygon P, a grid polygon exists with constant Hausdorff distance between their boundaries and their interiors. Moreover, we show that with a realistic input assumption we can also realize constant Fréchet distance between the boundaries. We present algorithms accompanying these constructions, heuristics to improve their output while keeping the distance bounds, and experiments to assess the output.

Quirijn W. Bouts, Irina Irina Kostitsyna, Marc van Kreveld, Wouter Meulemans, Willem Sonke, and Kevin Verbeek. Mapping Polygons to the Grid with Small Hausdorff and Fréchet Distance. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 22:1-22:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{bouts_et_al:LIPIcs.ESA.2016.22, author = {Bouts, Quirijn W. and Irina Kostitsyna, Irina and van Kreveld, Marc and Meulemans, Wouter and Sonke, Willem and Verbeek, Kevin}, title = {{Mapping Polygons to the Grid with Small Hausdorff and Fr\'{e}chet Distance}}, booktitle = {24th Annual European Symposium on Algorithms (ESA 2016)}, pages = {22:1--22:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-015-6}, ISSN = {1868-8969}, year = {2016}, volume = {57}, editor = {Sankowski, Piotr and Zaroliagis, Christos}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.22}, URN = {urn:nbn:de:0030-drops-63738}, doi = {10.4230/LIPIcs.ESA.2016.22}, annote = {Keywords: grid mapping, Hausdorff distance, Fr\'{e}chet distance, digital geometry} }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail