2 Search Results for "Morris-Wright, Rose"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.74
Drainability and Fillability of Polyominoes in Diverse Models of Global Control

Authors: Sándor P. Fekete, Peter Kramer, Jan-Marc Reinhardt, Christian Rieck, and Christian Scheffer

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
Tilt models offer intuitive and clean definitions of complex systems in which particles are influenced by global control commands. Despite a wide range of applications, there has been almost no theoretical investigation into the associated issues of filling and draining geometric environments. This is partly because a globally controlled system (i.e., passive matter) exhibits highly complex behavior that cannot be locally restricted. Thus, there is a strong need for theoretical studies that investigate these models both (1) in terms of relative power to each other, and (2) from a complexity theory perspective. In this work, we provide (1) general tools for comparing and contrasting different models of global control, and (2) both complexity and algorithmic results on filling and draining.
Cite as

Sándor P. Fekete, Peter Kramer, Jan-Marc Reinhardt, Christian Rieck, and Christian Scheffer. Drainability and Fillability of Polyominoes in Diverse Models of Global Control. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 74:1-74:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:LIPIcs.ICALP.2025.74,
  author =	{Fekete, S\'{a}ndor P. and Kramer, Peter and Reinhardt, Jan-Marc and Rieck, Christian and Scheffer, Christian},
  title =	{{Drainability and Fillability of Polyominoes in Diverse Models of Global Control}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{74:1--74:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.74},
  URN =		{urn:nbn:de:0030-drops-234518},
  doi =		{10.4230/LIPIcs.ICALP.2025.74},
  annote =	{Keywords: Global control, full Tilt, single Tilt, Fillability, Drainability, Polyominoes, Complexity}
}
Document
DOI: 10.4230/LIPIcs.SOCG.2015.16
Tilt: The Video - Designing Worlds to Control Robot Swarms with Only Global Signals

Authors: Aaron T. Becker, Erik D. Demaine, Sándor P. Fekete, Hamed Mohtasham Shad, and Rose Morris-Wright

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

Abstract
We present fundamental progress on the computational universality of swarms of micro- or nano-scale robots in complex environments, controlled not by individual navigation, but by a uniform global, external force. More specifically, we consider a 2D grid world, in which all obstacles and robots are unit squares, and for each actuation, robots move maximally until they collide with an obstacle or another robot. The objective is to control robot motion within obstacles, design obstacles in order to achieve desired permutation of robots, and establish controlled interaction that is complex enough to allow arbitrary computations. In this video, we illustrate progress on all these challenges: we demonstrate NP-hardness of parallel navigation, we describe how to construct obstacles that allow arbitrary permutations, and we establish the necessary logic gates for performing arbitrary in-system computations.
Cite as

Aaron T. Becker, Erik D. Demaine, Sándor P. Fekete, Hamed Mohtasham Shad, and Rose Morris-Wright. Tilt: The Video - Designing Worlds to Control Robot Swarms with Only Global Signals. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 16-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{becker_et_al:LIPIcs.SOCG.2015.16,
  author =	{Becker, Aaron T. and Demaine, Erik D. and Fekete, S\'{a}ndor P. and Shad, Hamed Mohtasham and Morris-Wright, Rose},
  title =	{{Tilt: The Video - Designing Worlds to Control Robot Swarms with Only Global Signals}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{16--18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.16},
  URN =		{urn:nbn:de:0030-drops-50870},
  doi =		{10.4230/LIPIcs.SOCG.2015.16},
  annote =	{Keywords: Particle swarms, global control, complexity, geometric computation}
}
  • Refine by Type
  • 2 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2015

  • Refine by Author
  • 2 Fekete, Sándor P.
  • 1 Becker, Aaron T.
  • 1 Demaine, Erik D.
  • 1 Kramer, Peter
  • 1 Morris-Wright, Rose
  • Show More...

  • Refine by Series/Journal
  • 2 LIPIcs

  • Refine by Classification
  • 1 Theory of computation → Computational geometry

  • Refine by Keyword
  • 1 Complexity
  • 1 Drainability
  • 1 Fillability
  • 1 Global control
  • 1 Particle swarms
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact