# What is the smallest diameter ring a non-convex polyhedron can pass through in 3-space?

The question is mostly in the title:

What is the smallest diameter ring a non-convex polyhedron can pass through in 3-space?

Imagine I have some non-convex polyhedron $P$, and I would like to find the smallest diameter ring that it can pass through in 3-space, undergoing any necessary rotations as it does so. Is there an efficient way to calculate $D_{ring}$? Pressing my luck, can I find the set of rotations for $P$ as it passes through the ring?

-

This is the "piano movers problem", also known as the motion planning problem, which has an enormous literature. Check out http://en.wikipedia.org/wiki/Motion_planning

-
Very cool, thanks! – UltraBlue06 Nov 30 '11 at 21:50

Just a side remark on convex polyhedra: Each of the regular polyhedra except the cube can pass through a circle of radius smaller than the smallest-radius cylinder circumscribing the polyhedron. This is proved in Tudor Zamfirescu's delightful paper, "Convex polytopes passing through circles" (PDF link). There is quite a nice (non-algorithmic) literature on this problem.

-
Thanks, I enjoyed reading the paper. =) – UltraBlue06 Dec 2 '11 at 19:19
Zamfirescu has a light touch despite deep thoughts. :-) – Joseph O'Rourke Dec 2 '11 at 20:33