Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

The question is mostly in the title.

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?

share|improve this question
add comment

2 Answers 2

up vote 6 down vote accepted

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

share|improve this answer
    
Very cool, thanks! –  UltraBlue06 Nov 30 '11 at 21:50
add comment

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.

share|improve this answer
1  
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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