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 > delta_1approx 0.901388 > delta_2approx 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 $delta_1le d < 1$, (c) $K$ cannot pass through $W$ by a purely translational motion but can do it when rotations are allowed when $delta_2 le d < delta_1$, and (d) $K$ cannot pass through $W$ at all when $d < delta_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)$.
تحميل البحث