Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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
---------------------------
share|improve this question
4  
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
5  
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

1 Answer 1

up vote 18 down vote accepted

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, SIAM Journal on Computing, volume 35, number 3, 2005, pages 531–566. (Link to preliminary 2003 arXiv version).

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; ...

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:
  Mitchell Table 1
This paper has 45 references, and surveys related milling and lawnmowing results.

share|improve this answer
    
Neat. I didn't think this problem had received so much attention. –  Alejandro Erickson Dec 11 '11 at 20:37
2  
Yes! When I was a kid and had to mow the lawn, I used to think about this sort of problem all the time... –  Todd Trimble Dec 11 '11 at 22:06
5  
I should clarify that this problem has not been studied because of its vacuuming applications (Roomba ignores this literature!), nor its lawnmowing applications, but because of its industrial applications, especially to milling. Joe Mitchell (with coauthors) has pursued these problems assiduously over the last decade. –  Joseph O'Rourke Dec 11 '11 at 22:37

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.