|
4
|
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? |
||
|
|
|
6
|
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 |
|||
|
|
5
|
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. |
||||||||
|
