Lawn mower problem

The lawn mower problem is a problem in algorithmic geometry . The question is clearly how to determine a route for a given area (a “lawn”) and a given lawnmower that mows the entire lawn and is the shortest of all possible routes.

The following terms are defined for formalization :

Given an area (a lawn ) . By discretization we assume that it consists of a finite number of multiply connected polygonal components . Note the number of corners with and the edge of . Also be given a lawnmower , that is, a polygon around a coordinate origin . For a with denote the placement of in , that is, the parallel shift of around the position vector of . ${\displaystyle R\subseteq \mathbb {R} ^{2}}$ ${\displaystyle R}$ ${\displaystyle n}$ ${\displaystyle \delta R}$ ${\displaystyle R}$ ${\displaystyle \chi }$ ${\displaystyle p\in \mathbb {R} ^{2}}$ ${\displaystyle \chi (p)}$ ${\displaystyle \chi }$ ${\displaystyle p}$ ${\displaystyle \chi }$ ${\displaystyle p}$

• A cutting Tour is then a curve , for each point by a placement of covers is. So (S) holds . ${\displaystyle \pi }$ ${\displaystyle R}$ ${\displaystyle \pi }$ ${\displaystyle R\subseteq \cup _{p\in \pi }\chi (p)}$

• Sometimes you are also interested in a milling tour . This means a cutting tour that does not “mow” any point outside of , that is, it applies (S) with equality . ${\displaystyle R}$
• The lawnmower problem asks for a minimum length cutting tour . The milling problem asks for a minimal milling tour or, alternatively, for proof that no milling tour exists.

Although many figures would be conceivable for the lawn mower, practically only the unit square and the unit circle are interesting and well investigated as a lawn mower.

• Simple observations
• 

  (Fig. 1) The milling problem

• 

  (Fig. 2) For combinatorially very simple lawn areas (here ) the combinatorial representation of the shortest cutting tour can potentially be of unlimited size. ${\displaystyle n=4}$

• 

  (Fig. 3) Axis-parallel lawn mowing and ...

• 

  (Fig. 4) ... mowing the lawn parallel to the edges.

Because of the phenomenon illustrated in Figure 2, the complexity of an input to the lawnmower problem is defined not as , but as the length of a numerical representation of the coordinates of the vertices of . With this understanding of the input variable, pseudopolynomial algorithms can be found that solve the lawnmower problem. ${\displaystyle n}$ ${\displaystyle R}$

Arkin, Fekete & Mitchell (2000) propose a reduction to the Hamilton circle problem in planar bipartite graphs with a maximum degree of 3 for the lawnmower problem . You then cite the argument of Johnson & Papadimitriou (1985) to prove that the lawnmower problem is NP-hard even for polygons . They also apply the same argument to the milling problem, but can only show there that it is NP-difficult for multi-connected polygonal areas. They also suggest a simple approximation algorithm for both problems:

Coverage of the plane with circular pixels. A solution to the round trip problem is shown in the graph . The optimal round trip provides an approximation for the lawnmower problem with circular lawnmowers. ${\displaystyle S}$

1. Determine a grid graph so that it contains the centers of those pixels that intersect with . ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle R}$
2. Use a known approximation method for the round trip problem .

Step 1 has a duration of , where is the power of . ${\displaystyle {\mathcal {O}}(s\log s)}$ ${\displaystyle s}$ ${\displaystyle S}$

literature

• EM Arkin, SP Fekete, JSB Mitchell: Approximation algorithms for lawn mowing and milling . In: Computational Geometry . 17, No. 1-2, 2000, pp. 25-50.
• DS Johnson, CH Papadimitriou: Computational complexity . In: The Traveling Salesman Problem . John-Wiley and Sons, Ltd., September 1985, ISBN 0471904139 , pp. 37-86.

Individual evidence

1. ^ Arkin, Fekete & Mitchell (2000), pp. 4-5
2. ^ Arkin, Fekete & Mitchell (2000), p. 5