research
∙
03/28/2023
Universal Coating in the 3D Hybrid Model
Motivated by the prospect of nano-robots that assist human physiological...
share
research
∙
10/11/2022
Morphing Planar Graph Drawings Through 3D
In this paper, we investigate crossing-free 3D morphs between planar str...
research
∙
05/16/2022
Unlabeled Multi-Robot Motion Planning with Tighter Separation Bounds
We consider the unlabeled motion-planning problem of m unit-disc robots ...
research
∙
03/13/2022
On the Computational Power of Energy-Constrained Mobile Robots: Algorithms and Cross-Model Analysis
We consider distributed systems of identical autonomous computational en...
research
∙
02/24/2022
The Shortest Path with Increasing Chords in a Simple Polygon
We study the problem of finding the shortest path with increasing chords...
research
∙
02/23/2022
Fast Reconfiguration for Programmable Matter
The concept of programmable matter envisions a very large number of tiny...
research
∙
08/31/2021
Embedding Ray Intersection Graphs and Global Curve Simplification
We prove that circle graphs (intersection graphs of circle chords) can b...
research
∙
05/27/2021
Separating Bounded and Unbounded Asynchrony for Autonomous Robots: Point Convergence with Limited Visibility
Among fundamental problems in the context of distributed computing by au...
research
∙
05/17/2021
Compacting Squares
Edge-connected configurations of squares are a common model for modular ...
research
∙
05/06/2021
Dots Boxes is PSPACE-complete
Exactly 20 years ago at MFCS, Demaine posed the open problem whether the...
research
∙
03/26/2021
Minimum Scan Cover and Variants – Theory and Experiments
We consider a spectrum of geometric optimization problems motivated by c...
research
∙
03/17/2021
Chasing Puppies: Mobile Beacon Routing on Closed Curves
We solve an open problem posed by Michael Biro at CCCG 2013 that was ins...
research
∙
01/15/2021
Preprocessing Imprecise Points for the Pareto Front
In the preprocessing model for uncertain data we are given a set of regi...
research
∙
09/02/2020
Turning machines
Molecular robotics is challenging, so it seems best to keep it simple. W...
research
∙
08/27/2020
Algorithmic Approaches to Reconfigurable Assembly Systems
Assembly of large scale structural systems in space is understood as cri...
research
∙
04/25/2020
Multi-robot motion planning of k-colored discs is PSPACE-hard
In the problem of multi-robot motion planning, a group of robots, placed...
research
∙
04/02/2020
Dots Polygons
We present a new game, Dots Polygons, played on a planar point set. ...
research
∙
10/22/2019
Folding Polyominoes with Holes into a Cube
When can a polyomino piece of paper be folded into a unit cube? Prior wo...
research
∙
05/03/2019
Most vital segment barriers
We study continuous analogues of "vitality" for discrete network flows/p...
research
∙
03/19/2019
Preprocessing Ambiguous Imprecise Points
Let R = {R_1, R_2, ..., R_n} be a set of regions and let X = {x_1, x_2,...
research
∙
01/09/2019
Fragile Complexity of Comparison-Based Algorithms
We initiate a study of algorithms with a focus on the computational comp...
research
∙
09/26/2018
On Optimal Min-# Curve Simplification Problem
In this paper we consider the classical min--# curve simplification prob...
research
∙
09/26/2018
Convex partial transversals of planar regions
We consider the problem of testing, for a given set of planar regions R...
research
∙
05/16/2018
Convex Hull Formation for Programmable Matter
We envision programmable matter as a system of nano-scale agents (called...
research
∙
05/03/2018
Approximating (k,ℓ)-center clustering for curves
The Euclidean k-center problem is a classical problem that has been exte...
research
∙
03/15/2018
An Optimal Algorithm to Compute the Inverse Beacon Attraction Region
The beacon model is a recent paradigm for guiding the trajectory of mess...
research
∙
12/26/2017
Folding Polyominoes into (Poly)Cubes
We study the problem of folding a polyomino P into a polycube Q, allowin...
research
∙
08/30/2017