# How to efficiently vacuum the house

Let $P$ be a polygon (perhaps with no acute angles inside) and let $L$ be a line segment. The segment may move through the area inside $P$ in straight lines, orthogonal to $L$, or it may pivot on any point on $L$ (while remaining entirely within $P$).

Let $S$ be a legal sequence of pivots and straight motions for $L$ in $P$, and say $S$ covers $P$ if applying the motions $S$ to $L$, passes over every part of the area in $P$. The covered area of $S$ is the cumulative area passed over by $L$.

1. How can we compute the minimum number of pivots over all covering sequences $S$?
2. How can we compute the minimum covered area over all covering sequences $S$?

Better formulations of the problem are welcome.

For a rectangular polygon, $h\times w$ and a line segment of length $l$, with $h < w$, and $l < h$. So in the best sequence I can think of the number of pivotes is $\lceil h/l \rceil$, and the second question is just a sum of areas of semicircles of radius $l$, plus the rectangular overlap from the last strip.

___________________________
| l-->                    | 1 pivot at each end
|                   <--l  |
| l-->                    |
|                   <--l  | 2 pivots if h is not integer multiple of l
---------------------------

• may I ask you if this question presented to you while concretely vacuuming the house? I think we should introduce a specific tag (e.g. "housework thoughs") – Pietro Majer Dec 11 '11 at 20:26
• Oddly enough, I was just eating breakfast. My girlfriend asked me why I looked lost in thought, and this is what I said to her. – Alejandro Erickson Dec 11 '11 at 20:39 