Consider a special lawnmower.  This lawnmower can go infinitely fast,
but has a finite possible acceleration in any direction.  What is the
optimal path for such a lawnmower to cut all the grass in a given
rectangle?  (Not a polygon, a rectangle).

Please note it is perfectly acceptable for the lawnmower
to cross over previously cut areas.

---

Clarification of Question by paulie111-ga on 19 Aug 2006 13:12 PDT

Thanks for your thoughts -

This is not really about a lawnmower, but has applications in many
areas of science - such as imaging and remote autonomous verhicles.

But allow me to clarify - yes - it has only a finite cutting swath -
say dimension with diameter A.  The rectangle has width B and C.  I
should not have said it can go infinitely fast - but rather, it's
speed is unlimited.

So if we consider a path like a raster pattern, it must accelerate
along each span, slow down (decelerate), turn and reaccelerate along
the next span.  In all these cases, acceleration is the limiting
factor.  It simply cannot turn 90 degrees as this would require
infinite acceleration.

A spiral overlaying a rectangle spends a large amount of time outside
the rectangle - and hence is probably not optimal.  A raster pattern
does not spend any time outside the rectangle, but has to slow down at
every turn, which is also probably not optimal.

Good luck with the thoughts!

---

Request for Question Clarification by pafalafa-ga on 19 Aug 2006 14:16 PDT

paulie111-ga,

Can you clarify what you mean by "optimal".  Least time?  Maximum lawn
cut per distance travel (i.e. smallest number of cross-overs)?  Fewest
changes in direction?

Also, if you explain the acceleration constraint a bit more, it would help.

Thanks,

pafalafa-ga

A spiral?

I assume also that its rate of deceleration in a given direction is
also finite and the same as its rate of acceleration.  The answer will
also depend on the dimensions of the rectangular lawn and the width of
the swath the lawnmower cuts with one pass.  Also, shall we assume the
lawnmower can turn 90 degrees in place or does it have a turning
radius?

For an finite surface area that is rectangular, a spiral might not be
optimal.  It could cause problems when you get the the edge of the
lawn.  Also, how does one account for going in a spiral?  You are
continually changing direction which involes decelerating in one
direction and accelerating in another?

Hi,
Since you are talking about a theoretical lawnmower, I presume you are
asking a theoretical question, i.e., that you are not interested in
the real practicalities of proper lawnmowing.  These are mowing
parallel with the sides where one turns to achieve a good cut there  -
two, three or four rows so that one can turn without bothering to try
to make a neat job in the turning area.
Obviously, if one wants to benefit from the speed of this lawnmower,
one should mow back and forth the longer length of the rectangle,
making as few turns as possible.
Maybe I have missed something in your statement:  "but has a finite
possible acceleration in any direction".  As Ansel has pointed out,
change in direction limits the speed; a reverse of direction and an
90° turn imply a dead stop.

Can you elucidate us?

Hi, again,
This is kind of a fun project, but I still think we need another clarification.
Ansel has raised the question about speed reduction in curves,
spiraling.  This is a limitation for actual vehicles.

1. Is it one for your lawnmower or a "remote autonomous vehicle"? 
(wouldn't seem to be one for electronic imaging)
2. Can the lawnmower go beyond the b,c dimensions of the lawn?

If the answers are 1. yes, 2. no; I still see no better solution that
a raster the major length of b,c.
If the answers are different, the problem could be more interesting.  
For example, it could be fastest to mow along the longer edge, making
a half circle to come back along the other side of the midfield
parallel line, turning back the same way to cut a swath parallel the
the first one, and so on, then racing to mow the corners.

I expect that my speculation is making the problem more difficult than
you anticipated.

If you can go over the rectangle to turn 180 degrees, you can take the
fewest stroke to cover it. (assuming there is a width of the lawnmower
to cover in a stroke) The mowing is neat but slower than using the
application of Graph Theory, which asks the maximum number of
intersection possibly made by finite number of line segments...

But in real life, if you do slappy mowing, you are fired anyway. So
"mathematically appropriate" path is not always the "socially
expected" path.