An area in the shape of a square 10 units on a side needs to be mowed. The mower, which only goes forward, has a mowing "footprint" that is a unit square, and turns about the center of its footprint.

An optimal mowing plan is sought. A mowing plan designates a starting position and from there gives a complete mowing path. An optimal mowing plan is one closest to a straight line in the sense that the sum of all the changes in the mower's angular direction is minimized, each such change taken as the minimum possible positive value. The mower is not impeded by the border of the square and can travel without difficulty outside it as well as inside it.

Is "spiral" better than "back and forth," and what about a "diagonal" plan?

(In reply to questions by Jer)

I think the second sentence of the problem statement pretty well describes the mower's turning: it pivots about the center of the 1x1 square that it cuts out, and the mower only goes straight ahead in the way that you would naturally think with the front side of the 1x1 square perpendicular to the mowing direction. Another way to think of the mowing is as "painting,"  with a square pad being used to apply the paint.

This problem is just supposed to be a way to have a little fun by comparing common ways that people use to mow lawns with respect to number of quarter turns the mower needs to make.  If there is some oddball mowing plan that gives dramatically better results, of course we would like to hear about it, but it seems more likely that the usual plans mentioned in the last sentence are at least close to the best possible. One other thing that is kinda fun is to cook up a mowing plan that is strikingly bad.

 

Posted by Richard on 2005-02-14 18:55:47