Publications (30)
Online Circle Packing
Sándor P. Fekete, Sven von Höveling, Christian Scheffer
We consider the online problem of packing circles into a square container. A sequence of circles has to be packed one at a time, without knowledge of the following incoming circles…
An Efficient Data Structure for Dynamic Two-Dimensional Reconfiguration
Sándor P. Fekete, Jan-Marc Reinhardt, Christian Scheffer
In the presence of dynamic insertions and deletions into a partially reconfigurable FPGA, fragmentation is unavoidable. This poses the challenge of developing efficient approaches…
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,…
Packing Disks into Disks with Optimal Worst-Case Density
Sándor P. Fekete, Phillip Keldenich, Christian Scheffer
We provide a tight result for a fundamental problem arising from packing disks into a circular container: The critical density of packing disks in a disk is 0.5. This implies that…
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…
Tile Reconfiguration by a Finite Automaton
Jonas Friemel, David Liedtke, Christian Scheffer
Shape formation is one of the most thoroughly studied problems in programmable matter and swarm robotics. However, in many models, the class of shapes that can be formed is highly…
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…
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…
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…
Packing Squares into a Disk with Optimal Worst-Case Density
Sándor P. Fekete, Vijaykrishna Gurunathan, Kushagra Juneja +3
We provide a tight result for a fundamental problem arising from packing squares into a circular container: The critical density of packing squares into a disk is $δ=\frac{8}{5Ï}…
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…
Connected Assembly and Reconfiguration by Finite Automata
Sándor P. Fekete, Eike Niehs, Christian Scheffer +1
We consider methods for connected reconfigurations by finite automate in the so-called \emph{hybrid} or \emph{Robot-on-Tiles} model of programmable matter, in which a number of sim…
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…
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…
Tilt Automata: Gathering Particles With Uniform External Control
Sándor P. Fekete, Jonas Friemel, Peter Kramer +3
Motivated by targeted drug delivery, we investigate the gathering of particles in the full tilt model of externally controlled motion planning: A set of particles is located at the…
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…
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…
New Geometric Algorithms for Fully Connected Staged Self-Assembly
Erik D. Demaine, Sándor P. Fekete, Christian Scheffer +1
We consider staged self-assembly systems, in which square-shaped tiles can be added to bins in several stages. Within these bins, the tiles may connect to each other, depending on…
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…
Universal Guard Problems
Sándor P. Fekete, Qian Li, Joseph S. B. Mitchell +1
We provide a spectrum of results for the Universal Guard Problem, in which one is to obtain a small set of points ("guards") that are "universal" in their ability to guard any of a…
Approximating the Integral Fréchet Distance
Anil Maheshwari, Jörg-Rüdiger Sack, Christian Scheffer
A pseudo-polynomial time -approximation algorithm is presented for computing the integral and average Fréchet distance between two given polygonal curves …
Coordinated Motion Planning: Reconfiguring a Swarm of Labeled Robots with Bounded Stretch
Erik D. Demaine, Sándor P. Fekete, Phillip Keldenich +2
We present a number of breakthroughs for coordinated motion planning, in which the objective is to reconfigure a swarm of labeled convex objects by a combination of parallel, conti…
Conflict-Free Coloring of Planar Graphs
Zachary Abel, Victor Alvarez, Aman Gour +5
A conflict-free k-coloring of a graph assigns one of k different colors to some of the vertices such that, for every vertex v, there is a color that is assigned to exactly one vert…
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…
CADbots: Algorithmic Aspects of Manipulating Programmable Matter with Finite Automata
Sándor P. Fekete, Robert Gmyr, Sabrina Hugo +3
We contribute results for a set of fundamental problems in the context of programmable matter by presenting algorithmic methods for evaluating and manipulating a collective of part…
Worst-Case Optimal Covering of Rectangles by Disks
Sándor P. Fekete, Utkarsh Gupta, Phillip Keldenich +2
We provide the solution for a fundamental problem of geometric optimization by giving a complete characterization of worst-case optimal disk coverings of rectangles: For any $λ\ge…
Split Packing: Algorithms for Packing Circles with Optimal Worst-Case Density
Sándor P. Fekete, Sebastian Morr, Christian Scheffer
In the classic circle packing problem, one asks whether a given set of circles can be packed into a given container. Packing problems like this have been shown to be -…
Similarity of Polygonal Curves in the Presence of Outliers
Jean-Lou De Carufel, Amin Gheibi, Anil Maheshwari +2
The Fréchet distance is a well studied and commonly used measure to capture the similarity of polygonal curves. Unfortunately, it exhibits a high sensitivity to the presence of ou…
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…
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…