5 papers
The Freeze-Tag Problem: How to Wake Up a Swarm of Robots
Esther M. Arkin, Michael A. Bender, Sandor P. Fekete +2
An optimization problem that naturally arises in the study of swarm robotics is the Freeze-Tag Problem (FTP) of how to awaken a set of ``asleep'' robots, by having an awakened robo…
Optimal Covering Tours with Turn Costs
Esther M. Arkin, Michael A. Bender, Erik D. Demaine +3
We give the first algorithmic study of a class of ``covering tour'' problems related to the geometric Traveling Salesman Problem: Find a polygonal tour for a cutter so that it swee…
On the Reflexivity of Point Sets
Esther M. Arkin, Sandor P. Fekete, Ferran Hurtado +4
We introduce a new measure for planar point sets S that captures a combinatorial distance that S is from being a convex set: The reflexivity rho(S) of S is given by the smallest nu…
An Algorithmic Study of Manufacturing Paperclips and Other Folded Structures
Esther M. Arkin, Sandor P. Fekete, Joseph S. B. Mitchell
We study algorithmic aspects of bending wires and sheet metal into a specified structure. Problems of this type are closely related to the question of deciding whether a simple non…
When Can You Fold a Map?
Esther M. Arkin, Michael A. Bender, Erik D. Demaine +4
We explore the following problem: given a collection of creases on a piece of paper, each assigned a folding direction of mountain or valley, is there a flat folding by a sequence…