  We consider geometric collision-detection problems for modular reconfigurable
robots. Assuming the nodes (modules) are connected squares on a grid, we
investigate the complexity of deciding whether collisions may occur, or can be
avoided, if a set of expansion and contraction operations is executed. We study
both discrete- and continuous-time models, and allow operations to be coupled
into a single parallel group. Our algorithms to decide if a collision may occur
run in $O(n^2\log^2 n)$ time, $O(n^2)$ time, or $O(n\log^2 n)$ time, depending
on the presence and type of coupled operations, in a continuous-time model for
a modular robot with $n$ nodes. To decide if collisions can be avoided, we show
that a very restricted version is already NP-complete in the discrete-time
model, while the same problem is polynomial in the continuous-time model. A
less restricted version is NP-hard in the continuous-time model.
