On the complexity of the free space of a translating square in R^3

Abstract: Consider a polyhedral robot $B$ that can translate (without rotating) amidst a finite set of non-moving polyhedral obstacles in $\mathbb R^3$. The "free space" $\mathcal F$ of $B$ is the set of all positions in which $B$ is disjoint from the interior of every obstacle. Aronov and Sharir (1997) derived an upper bound of $O(n^2\log n)$ for the combinatorial complexity of $\mathcal F$, where $n$ is the total number of vertices of the obstacles, and the complexity of $B$ is assumed constant. Halperin and Yap (1993) showed that, if $B$ is either a "flat" convex polygon or a three-dimensional box, then a tighter bound of $O(n^2\alpha(n))$ holds. Here $\alpha(n)$ is the inverse Ackermann function. In this paper we prove that if $B$ is a square (or a rectangle or a parallelogram), then the complexity of $\mathcal F$ is $O(n^2)$. We conjecture that this bound holds more generally if $B$ is any convex polygon whose edges come in parallel pairs. For such polygons $B$, the only triple contacts whose number we were not able to bound by $O(n^2)$ are those made by three mutually non-parallel edges of $B$. Similarly, for the case where $B$ is a cube (or a box or a parallelepiped), we bound by $O(n^2)$ all triple contacts except those made by three mutually non-parallel edges of $B$.