Return to Answer

Concerning nonconvex $C$, I posed it as an open-problem exercise in Computational Geometry in C to determine the worst polygon (or, equivalently, the worst polygonal curve $C$), worst in the number of "moves," to get $C$ through the doorway interval (p.321, Ex.4). I defined a "move" as monotonic $x$ and $y$ translation and $\theta$ rotation. The idea was to try to find a shape that requires many reversals. At that time this was only known to lie between $\Omega(n)$ and $O(n^2)$ moves for a polygon of $n$ vertices, and I am unaware of any subsequent improvements.

For the $O(n^2)$ upper bound, see:

Yap, Chee-Keng. "How to move a chair through a door." IEEE Journal of Robotics and Automation (1987): 172-181. (IEEE link)

This paper also computes the minimum door width for an $n$-gon with an $O(n^2)$-time algorithm.

Concerning nonconvex $C$, I posed it as an open-problem exercise in Computational Geometry in C to determine the worst polygon (or, equivalently, the worst polygonal curve $C$), worst in the number of "moves," to get $C$ through the doorway interval (p.321, Ex.4). I defined a "move" as monotonic $x$ and $y$ translation and $\theta$ rotation. The idea was to try to find a shape that requires many reversals. At that time the number of "backups" was only known to lie between $\Omega(n)$ and $O(n^2)$ moves for a polygon of $n$ vertices, and I am unaware of any subsequent improvements.

For the $O(n^2)$ upper bound, see:

Yap, Chee-Keng. "How to move a chair through a door." IEEE Journal of Robotics and Automation (1987): 172-181. (IEEE link)

This paper also computes the minimum door width for an $n$-gon with an $O(n^2)$-time algorithm.

Concerning nonconvex $C$, I posed it as an open-problem exercise in Computational Geometry in C to determine the worst polygon (or, equivalently, the worst polygonal curve $C$), worst in the number of "moves," to get $C$ through the doorway interval (p.321, Ex.4). I defined a "move" as monotonic $x$ and $y$ translation and $\theta$ rotation. The idea was to try to find a shape that requires many reversals. At that time this was only known to lie between $\Omega(n)$ and $O(n^2)$ moves for a polygon of $n$ vertices, and I am unaware of any subsequent improvements.

For the $O(n^2)$ upper bound, see:

Yap, Chee-Keng. "How to move a chair through a door." IEEE Journal of Robotics and Automation (1987): 172-181. (IEEE link)

This paper also computes the minimum door width for an $n$-gon with an $O(n^2)$-time algorithm.

Concerning nonconvex $C$, I posed it as an open-problem exercise in Computational Geometry in C to determine the worst polygon (or, equivalently, the worst polygonal curve $C$), worst in the number of "moves," to get $C$ through the doorway interval (p.321, Ex.4). I defined a "move" as monotonic $x$ and $y$ translation and $\theta$ rotation. The idea was to try to find a shape that requires many reversals. At that time this was only known to lie between $\Omega(n)$ and $O(n^2)$ moves for a polygon of $n$ vertices, and I am unaware of any subsequent improvements.

For the $O(n^2)$ upper bound, see:

Yap, Chee-Keng. "How to move a chair through a door." IEEE Journal of Robotics and Automation (1987): 172-181. (IEEE link)

This paper also computes the minimum door width for an $n$-gon with an $O(n^2)$-time algorithm.

Concerning nonconvex $C$, I posed it as an open-problem exercise in Computational Geometry in C to determine the worst polygon (or, equivalently, the worst polygonal curve $C$), worst in the number of "moves," to get $C$ through the doorway interval (p.321, Ex.4). I defined a "move" as monotonic $x$ and $y$ translation and $\theta$ rotation. The idea was to try to find a shape that requires many reversals. At that time this was only known to lie between $\Omega(n)$ and $O(n^2)$ moves for a polygon of $n$ vertices, and I am unaware of any subsequent improvements.

For the $O(n^2)$ upper bound, see:

Yap, Chee-Keng. "How to move a chair through a door." IEEE Journal of Robotics and Automation (1987): 172-181. (IEEE link)

This paper also computes the minimum door width for an $n$-gon with an $O(n^2)$-time algorithm.

Concerning nonconvex $C$, I posed it as an open-problem exercise in Computational Geometry in C to determine the worst polygon (or, equivalently, the worst polygonal curve $C$), worst in the number of "moves," to get $C$ through the doorway interval (p.321, Ex.4). I defined a "move" as monotonic $x$ and $y$ translation and $\theta$ rotation. The idea was to try to find a shape that requires many reversals. At that time this was only known to lie between $\Omega(n)$ and $O(n^2)$ moves for a polygon of $n$ vertices, and I am unaware of any subsequent improvements.

For the $O(n^2)$ upper bound, see:

Yap, Chee-Keng. "How to move a chair through a door." IEEE Journal of Robotics and Automation (1987): 172-181. (IEEE link)

This paper also computes the minimum door width for an $n$-gon with an $O(n^2)$-time algorithm.