5
$\begingroup$

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?

$\endgroup$
7
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
5
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Zamfirescu has a light touch despite deep thoughts. :-) $\endgroup$ – Joseph O'Rourke Dec 2 '11 at 20:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.