Skip to main content
4 of 4
Quote explicit complexity.
Joseph O'Rourke
  • 150.9k
  • 36
  • 358
  • 958

A supplement to Ian's answer: Here is the largest-area sofa known, due to Gerver:


![GerverSofa][1]

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:


            ![Piano][2]

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
  • 150.9k
  • 36
  • 358
  • 958