1 citations · 1 across the 13 of their papers we have counts for
21 papers
Restless Guards: Robust Guarding of Polyominoes
Linda Kleist, Ramin Kosfeld, Christian Rieck
The art gallery problem is a fundamental problem whose practical applications have inspired numerous variants. In this work, we investigate a setting in which full coverage of the…
Moving Matter: Using a Single, Simple Robot to Reconfigure a Connected Set of Building Blocks
Javier Garcia, Jonas Friemel, Ramin Kosfeld +9
We implement and evaluate different methods for the reconfiguration of a connected arrangement of tiles into a desired target shape, using a single active robot that can move along…
Guarding Offices with Maximum Dispersion
Sándor P. Fekete, Kai Kobbe, Dominik Krupke +3
We investigate the Dispersive Art Gallery Problem with vertex guards and rectangular visibility (-visibility) for a class of orthogonal polygons that reflect the properties of r…
Drainability and Fillability of Polyominoes in Diverse Models of Global Control
Sándor P. Fekete, Peter Kramer, Jan-Marc Reinhardt +2
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 b…
Efficient Reconfiguration of Tile Arrangements by a Single Active Robot
Aaron T. Becker, Sándor P. Fekete, Jonas Friemel +6
We consider the problem of reconfiguring a two-dimensional connected grid arrangement of passive building blocks from a start configuration to a goal configuration, using a single…
Sliding Squares in Parallel
Hugo A. Akitaya, Sándor P. Fekete, Peter Kramer +4
We consider algorithmic problems motivated by modular robotic reconfiguration in the sliding square model, in which we are given square-shaped modules in a (labeled or unlabele…
Coordinated Motion Planning: Multi-Agent Path Finding in a Densely Packed, Bounded Domain
Sándor P. Fekete, Ramin Kosfeld, Peter Kramer +3
We study Multi-Agent Path Finding for arrangements of labeled agents in the interior of a simply connected domain: Given a unique start and target position for each agent, the goal…
Targeted Drug Delivery: Algorithmic Methods for Collecting a Swarm of Particles with Uniform External Forces
Aaron T. Becker, Sándor P. Fekete, Li Huang +5
We investigate algorithmic approaches for targeted drug delivery in a complex, maze-like environment, such as a vascular system. The basic scenario is given by a large swarm of mic…
On the Connectivity of the Flip Graph of Plane Spanning Paths
Linda Kleist, Peter Kramer, Christian Rieck
Flip graphs of non-crossing configurations in the plane are widely studied objects, e.g., flip graph of triangulations, spanning trees, Hamiltonian cycles, and perfect matchings. T…
Dispersive Vertex Guarding for Simple and Non-Simple Polygons
Sándor P. Fekete, Joseph S. B. Mitchell, Christian Rieck +2
We study the Dispersive Art Gallery Problem with vertex guards: Given a polygon , with pairwise geodesic Euclidean vertex distance of at least , and a rational numb…
Guarding Polyominoes Under -Hop Visibility
Omrit Filtser, Erik Krohn, Bengt J. Nilsson +2
We study the Art Gallery Problem under -hop visibility in polyominoes. In this visibility model, two unit squares of a polyomino can see each other if and only if the shortest p…
The Lawn Mowing Problem: From Algebra to Algorithms
Sándor P. Fekete, Dominik Krupke, Michael Perk +2
For a given polygonal region , the Lawn Mowing Problem (LMP) asks for a shortest tour that gets within Euclidean distance 1/2 of every point in ; this is equivalent to co…
A Closer Cut: Computing Near-Optimal Lawn Mowing Tours
Sándor P. Fekete, Dominik Krupke, Michael Perk +2
For a given polygonal region , the Lawn Mowing Problem (LMP) asks for a shortest tour that gets within Euclidean distance 1 of every point in ; this is equivalent to comp…
Reconfiguration of a 2D Structure Using Spatio-Temporal Planning and Load Transferring
Javier Garcia, Michael Yannuzzi, Peter Kramer +3
We present progress on the problem of reconfiguring a 2D arrangement of building material by a cooperative group of robots. These robots must avoid collisions, deadlocks, and are s…
Efficiently Reconfiguring a Connected Swarm of Labeled Robots
Sándor P. Fekete, Peter Kramer, Christian Rieck +2
When considering motion planning for a swarm of labeled robots, we need to rearrange a given start configuration into a desired target configuration via a sequence of parallel,…
The Dispersive Art Gallery Problem
Christian Rieck, Christian Scheffer
We introduce a new variant of the art gallery problem that comes from safety issues. In this variant we are not interested in guard sets of smallest cardinality, but in guard sets…
Connected Reconfiguration of Polyominoes Amid Obstacles using RRT*
Javier Garcia, Michael Yannuzzi, Peter Kramer +2
This paper investigates the use of a sampling-based approach, the RRT*, to reconfigure a 2D set of connected tiles in complex environments, where multiple obstacles might be presen…
Connected Coordinated Motion Planning with Bounded Stretch
Sándor P. Fekete, Phillip Keldenich, Ramin Kosfeld +2
We consider the problem of connected coordinated motion planning for a large collective of simple, identical robots: From a given start grid configuration of robots, we need to rea…
Particle-Based Assembly Using Precise Global Control
Jakob Keller, Christian Rieck, Christian Scheffer +1
In micro- and nano-scale systems, particles can be moved by using an external force like gravity or a magnetic field. In the presence of adhesive particles that can attach to each…
Don't Rock the Boat: Algorithms for Balanced Dynamic Loading and Unloading
Sándor P. Fekete, Sven von Höveling, Joseph S. B. Mitchell +4
We consider dynamic loading and unloading problems for heavy geometric objects. The challenge is to maintain balanced configurations at all times: minimize the maximal motion of th…
Tilt Assembly: Algorithms for Micro-Factories That Build Objects with Uniform External Forces
Aaron T. Becker, Sándor P. Fekete, Phillip Keldenich +4
We present algorithmic results for the parallel assembly of many micro-scale objects in two and three dimensions from tiny particles, which has been proposed in the context of prog…