There is a right angle corner with width 1 in both directions. One wants to find the largest area shape which can pass through this corner. I know that this is a famous problem, but what is it called?
Asked
Active
Viewed 1,549 times
8
Ricardo Andrade
- 6,139
Yijun Yuan
- 569
-
Manhole problem ? – Hachino Apr 01 '15 at 14:19
-
@Hachino Actually not... The right ans is from Ian Farrell. – Yijun Yuan Apr 01 '15 at 14:22
-
A 13-minute-long video featuring Dan Romik on the Moving Sofa Problem. – Rodrigo de Azevedo Jun 05 '17 at 13:59
2 Answers
9
A supplement to Ian's answer: Here is the largest-area sofa known, due to Gerver:
Gerver, Joseph L. (1992). "On Moving a Sofa Around a Corner". Geometriae Dedicata 42 (3): 267–283. (Springer link.)
Added (triggered by @GeraldEdgar's remark). The computational complexity of algorithms grows exponentially in the dimension, about $n^5$ for polyhedral objects with $n$ vertices moving in $\mathbb{R}^3$. Here is an algorithm moving an $n{=}4500$-triangle piano through a challenging apartment requiring several tricky maneuvers:
Kuffner, James J., and Steven M. LaValle. "RRT-connect: An efficient approach to single-query path planning." Robotics and Automation, 2000. Proceedings. ICRA'00. IEEE International Conference on. Vol. 2. IEEE, 2000. (IEEE link.)
Not surprisingly, the problem is also called The Piano Mover's Problem.
Joseph O'Rourke
- 149,182
- 34
- 342
- 933
-
1Manifestly, to find the largest solid that would pass through a unit cube corner, the solution would be obtained by endowing the largest-area sofa known with height 1. – Bob Spaghetti Apr 01 '15 at 19:53
-
1New (Jun 2017) paper by Yoav Kallus and Dan Romik: "Improved upper bounds in the moving sofa problem," arXiv abstract. – Joseph O'Rourke Jun 22 '17 at 19:25
8
The Moving sofa problem, I believe.
Bob Spaghetti
- 440
-
4From personal experience ... sofas move in 3 dimensions. Many years ago another mathematician was helping me move. We had to carry a sofa up a flight of stairs, then turn a corner at the top. It didn't fit. But he says, "Just rotate it this way..." and it did fit. I still don't know what he did. – Gerald Edgar Apr 01 '15 at 16:03
-
An instance where transseries wouldn't have helped, I suppose. Gerhard "Guess Geometry's Good For Something" Paseman, 2015.04.01 – Gerhard Paseman Apr 01 '15 at 18:22