17
$\begingroup$

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
---------------------------
$\endgroup$
2
  • 5
    $\begingroup$ 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") $\endgroup$ Dec 11, 2011 at 20:26
  • 6
    $\begingroup$ 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. $\endgroup$ Dec 11, 2011 at 20:39

1 Answer 1

21
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Neat. I didn't think this problem had received so much attention. $\endgroup$ Dec 11, 2011 at 20:37
  • 3
    $\begingroup$ Yes! When I was a kid and had to mow the lawn, I used to think about this sort of problem all the time... $\endgroup$
    – Todd Trimble
    Dec 11, 2011 at 22:06
  • 8
    $\begingroup$ 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. $\endgroup$ Dec 11, 2011 at 22:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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