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$.
- How can we compute the minimum number of pivots over all covering sequences $S$?
- 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
---------------------------
Best Answer
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).
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:
This paper has 45 references, and surveys related milling and lawnmowing results.