How to efficiently vacuum the house - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T00:01:40Z http://mathoverflow.net/feeds/question/83200 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/83200/how-to-efficiently-vacuum-the-house How to efficiently vacuum the house Alejandro Erickson 2011-12-11T20:04:33Z 2011-12-11T20:25:17Z <p>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$). </p> <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$.</p> <ol> <li>How can we compute the minimum number of pivots over all covering sequences $S$?</li> <li>How can we compute the minimum covered area over all covering sequences $S$?</li> </ol> <p>Better formulations of the problem are welcome.</p> <p>For a rectangular polygon, $h\times w$ and a line segment of length $l$, with $h &lt; w$, and $l &lt; 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.</p> <pre><code>___________________________ | l--&gt; | 1 pivot at each end | &lt;--l | | l--&gt; | | &lt;--l | 2 pivots if h is not integer multiple of l --------------------------- </code></pre> http://mathoverflow.net/questions/83200/how-to-efficiently-vacuum-the-house/83204#83204 Answer by Joseph O'Rourke for How to efficiently vacuum the house Joseph O'Rourke 2011-12-11T20:25:17Z 2011-12-11T20:25:17Z <p>This problem and variants were extensively explored in the paper "Optimal Covering Tours with Turn Costs," by Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Sandor P. Fekete, Joseph S. B. Mitchell, Saurabh Sethia, <em>SIAM Journal on Computing</em>, volume 35, number 3, 2005, pages 531–566. (Link to preliminary 2003 <a href="http://arxiv.org/abs/cs.DS/0309014" rel="nofollow">arXiv</a> version).</p> <blockquote> <p>We prove that the covering tour problem with turn costs is NP-complete, even if the objective is purely to minimize the number of turns, the pocket is orthogonal (rectilinear), and the cutter must move axis-parallel. The hardness of the problem is not apparent, as our problem seemingly bears a close resemblance to the polynomially solvable Chinese postman problem; ... </p> </blockquote> <p>Almost every variant is NP-complete/hard, so the concentration has been on approximations. To give a sense of the bewildering variety of results, here is a table from the above paper: <br />&nbsp; <img src="http://people.csail.mit.edu/~orourke/MathOverflow/MitchellTable1.jpg" alt="Mitchell Table 1"> <br /> This paper has 45 references, and surveys related milling and lawnmowing results.</p>