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?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
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

Improve this answer
$\endgroup$
0
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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Zamfirescu has a light touch despite deep thoughts. :-) $\endgroup$
    – Joseph O'Rourke
    Commented Dec 2, 2011 at 20:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .