Optimal way to cut grass on the rectangular area.

Question

A field of grass has sizes 25 metres $\times$ 40 metres. A lawnmower can cut 40 cm at width. Lazy gardener wants to cut the field of grass by pushing the mower with minimum distance. How should he cut the grass? I was wondering if he goes along straight lines and then turn the mower such that it manages to cut exactly all the grasses on the boundary. But I was unable to prove that the strategy is optimal.

Answer 1

Just a tangential note: Your particular problem, and many natural variants, are NP-hard for regions more complicated than rectangles.

Arkin, Esther M., Michael A. Bender, Erik D. Demaine, Sándor P. Fekete, Joseph SB Mitchell, and Saurabh Sethia. "Optimal covering tours with turn costs." SIAM Journal on Computing 35, no. 3 (2005): 531-566. (arXiv abs.)

Arkin, Esther M., Sándor P. Fekete, and Joseph SB Mitchell. "Approximation algorithms for lawn mowing and milling." Computational Geometry 17, no. 1-2 (2000): 25-50. (Journal link.)

---

         

---