We present the first universal reconfiguration algorithm for transforming a modular robot between any two facet-connected square-grid configurations using pivot moves. More precisely, we show that five extra “helper” modules (“musketeers”) suffice to reconfigure the remaining n modules between any two given configurations. Our algorithm uses $$O(n^2)$$ pivot moves, which is worst-case optimal. Previous reconfiguration algorithms either require less restrictive “sliding” moves, do not preserve facet-connectivity, or for the setting we consider, could only handle a small subset of configurations defined by a local forbidden pattern. Configurations with the forbidden pattern do have disconnected reconfiguration graphs (discrete configuration spaces), and indeed we show that they can have an exponential number of connected components. But forbidding the local pattern throughout the configuration is far from necessary, as we show that just a constant number of added modules (placed to be freely reconfigurable) suffice for universal reconfigurability. We also classify three different models of natural pivot moves that preserve facet-connectivity, and show separations between these models.

We introduce the study of forcing sets in mathematical origami. The origami material folds flat along straight line segments called creases, each of which is assigned a folding direction of mountain or valley. A subset F of creases is forcing if the global folding mountain/valley assignment can be deduced from its restriction to F. In this paper we focus on one particular class of foldable patterns called Miura-ori, which divide the plane into congruent parallelograms using horizontal lines and zigzag vertical lines. We develop efficient algorithms for constructing a minimum forcing set of a Miura-ori map, and for deciding whether a given set of creases is forcing or not. We also provide tight bounds on the size of a forcing set, establishing that the standard mountain-valley assignment for the Miura-ori is the one that requires the most creases in its forcing sets. Additionally, given a partial mountain/valley assignment to a subset of creases of a Miura-ori map, we determine whether the assignment domain can be extended to a locally flat-foldable pattern on all the creases. At the heart of our results is a novel correspondence between flat-foldable Miura-ori maps and 3-colorings of grid graphs.

For a set of points in the plane and a fixed integer k > 0, the Yao graph Yk partitions the space around each point into k equiangular cones of angle θ = 2π/k, and connects each point to a nearest neighbor in each cone. It is known for all Yao graphs, with the sole exception of Y5, whether or not they are geometric spanners. In this paper we close this gap by showing that for odd k ≥ 5, the spanning ratio of Yk is at most 1/(1−2sin(3θ/8)), which gives the first constant upper bound for Y5, and is an improvement over the previous bound of 1/(1−2sin(θ/2)) for odd k ≥ 7. We further reduce the upper bound on the spanning ratio for Y5 from 10.9 to 2 + √3 ≈ 3.74, which falls slightly below the lower bound of 3.79 established for the spanning ratio of ⊝5 (⊝-graphs differ from Yao graphs only in the way they select the closest neighbor in each cone). This is the first such separation between a Yao and ⊝-graph with the same number of cones. We also give a lower bound of 2.87 on the spanning ratio of Y5. Finally, we revisit the Y6 graph, which plays a particularly important role as the transition between the graphs (k > 6) for which simple inductive proofs are known, and the graphs (k ≤ 6) whose best spanning ratios have been established by complex arguments. Here we reduce the known spanning ratio of Y6 from 17.6 to 5.8, getting closer to the spanning ratio of 2 established for ⊝6.

Let P be a set of n points in the plane. The Yao graph for P is a geometric graph obtained by extending equally spaced rays from each point u ∊ P, and connecting u to a closest neighbor in each sector formed by these rays. Associated to this graph is an integer parameter k > 1 defining the number of rays. The out-degree of the Yao graph is k, but the in-degree can be as large as n − 1. To overcome the problem of potential high in-degree, the Sparse-Yao graph (also known as Yao-Yao graph) eliminates from the Yao graph all but a shortest incoming edge in each sector. It has been established that the Yao graph defined by integer parameter k ≥ 6 is a t-spanner, for some real constant t > 1, meaning that it has a path between each pair of points in P of length at most t times the Euclidean distance between the two points. The constant t is called the stretch factor of the Yao graph. The problem of determining whether the Sparse-Yao graph is a spanner or not has been long open. In this paper we make progress on this problem by showing that the Sparse-Yao graph defined by integer parameter 6k, with k ≥ 6, is a spanner with stretch factor 11.67. With parameter k ≥ 8, the stretch factor drops to 4.75.

We introduce the problem of shape replication in the Wang tile self-assembly model. Given an input shape, we consider the problem of designing a self-assembly system which will replicate that shape into either a specific number of copies, or an unbounded number of copies. Motivated by practical DNA implementations of Wang tiles, we consider a model in which tiles consisting of DNA or RNA can be dynamically added in a sequence of stages. We further permit the addition of RNase enzymes capable of disintegrating RNA tiles. Under this model, we show that arbitrary genus-0 shapes can be replicated infinitely many times using only O(1) distinct tile types and O(1) stages. Further, we show how to replicate precisely n copies of a shape using O(log n) stages and O(1) tile types.

We propose a new low-interference topology for wireless ad hoc networks modeled by Quasi Unit Disk Graphs (qUDGs). Our topology combines two existing structures, the relaxed Greedy structure developed by Damian, Pandit and Pemmaraju, and the low-interference structure developed by Burkhart, von Rickenbach, Wattenhofer and Zollinger. Our main contribution is showing that, when applied on a qUDG G = (V, E), this new structure inherits most properties of the two underlying structures: (a) it is a t(1+ε) spanner of G, for any t > 1 and ε > 0, (ii) it has optimal interference among all t-spanners for G, (iii) it has O(1) maximum degree, (iv) its total weight is within a factor of O(log n) of the weight of a minimum spanning tree for V, and (v) it can be implemented efficiently in O(log n) rounds of communication.

We show that the space of polygonizations of a fixed planar point set $S$ of $n$ points is connected by $O(n^2)$ ``moves'' between simple polygons. Each move is composed of a sequence of atomic moves called ``stretches'' and ``twangs''. These atomic moves walk between weakly simple ``polygonal wraps'' of $S$. These moves show promise to serve as a basis for generating random polygons.

This paper presents a distributed algorithm for wireless ad-hoc networks that runs in polylogarithmic number of rounds in the size of the network and constructs a lightweight, linear size, (1+ε)-spanner for any given ε> 0. A wireless network is modeled by a d-dimensional α-quasi unit ball graph (α-UBG), which is a higher dimensional generalization of the standard unit disk graph (UDG) model. The d-dimensional α-UBG model goes beyond the unrealistic “flat world ” as-sumption of UDGs and also takes into account transmission errors, fading signal strength, and physical obstructions. The main result in the paper is this: for any fixed ε> 0, 0 < α ≤ 1, and d ≥ 2 there is a distributed algorithm run-ning in O(log n·log ∗ n) communication rounds on an n-node, d-dimensional α-UBG G that computes a (1+ε)-spanner G′ of G with maximum degree Δ(G′) = O(1) and total weight w(G′) = O(w(MST (G)). This result is motivated by the topology control problem in wireless ad-hoc networks and improves on existing topology control algorithms along sev-eral dimensions. The technical contributions of the paper include a new, sequential, greedy algorithm with relaxed edge ordering and lazy updating, and clustering techniques for filtering out unnecessary edges.