6
$\begingroup$

Question: Given a closed curve C, what will be the (bounds on) dimension of the interval it will pass through?

i.e. which are the necessary and sufficient conditions for a planar compact set C to pass through a closed interval in a plane?

The matter has been studied in the 1982 paper by Gilbert Strang, "The width of a chair," in Amer. Math. Monthly; but only ends in certain (interesting) conjectures in case of a non convex C (the problem in case of a convex C does get a definitive answer as its shortest orthogonal chord).

A development over this question would be the still open moving sofa problem (Leo Moser's 1966 problem, "Moving Furniture through a Hallway," Problem 66-11 in SIAM Review).

Does the question have a definitive answer? Any references/latest work done with regards to the question are welcome.

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks. Is their any information on non-polygonal curves in respect of the time complexity in calculating their door width. $\endgroup$
    – ARi
    Commented Sep 16, 2013 at 10:50
  • $\begingroup$ @ARi: Not that I know of. It would be difficult to measure the complexity for smooth curves. I guess it would have to be in terms of the degree of an algebraic curve and the bit-size of the coefficients. $\endgroup$
    – Joseph O'Rourke
    Commented Sep 16, 2013 at 11:31

You must log in to answer this question.

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