Throwing a Sofa Through the Window
We study several variants of the problem of moving a convex polytope $K$, with $n$ edges, in three dimensions through a flat rectangular (and sometimes more general) window. Specifically: $\bullet$ We study variants where the motion is restricted to translations only, discuss situations where such a motion can be reduced to sliding (translation in a fixed direction), and present efficient algorithms for those variants, which run in time close to $O(n^{8/3})$. $\bullet$ We consider the case of a `gate' (an unbounded window with two parallel infinite edges), and show that $K$ can pass through such a window, by any collision-free rigid motion, if and only if it can slide through it. $\bullet$ We consider arbitrary compact convex windows, and show that if $K$ can pass through such a window $W$ (by any motion) then $K$ can slide through a gate of width equal to the diameter of $W$. $\bullet$ We study the case of a circular window $W$, and show that, for the regular tetrahedron $K$ of edge length $1$, there are two thresholds $1 > δ_1\approx 0.901388 > δ_2\approx 0.895611$, such that (a) $K$ can slide through $W$ if the diameter $d$ of $W$ is $\ge 1$, (b) $K$ cannot slide through $W$ but can pass through it by a purely translational motion when $δ_1\le d < 1$, (c) $K$ cannot pass through $W$ by a purely translational motion but can do it when rotations are allowed when $δ_2 \le d < δ_1$, and (d) $K$ cannot pass through $W$ at all when $d < δ_2$. $\bullet$ Finally, we explore the general setup, where we want to plan a general motion (with all six degrees of freedom) for $K$ through a rectangular window $W$, and present an efficient algorithm for this problem, with running time close to $O(n^4)$.