  For a given polygonal region $P$, the Lawn Mowing Problem (LMP) asks for a
shortest tour $T$ that gets within Euclidean distance 1/2 of every point in
$P$; this is equivalent to computing a shortest tour for a unit-diameter cutter
$C$ that covers all of $P$. As a generalization of the Traveling Salesman
Problem, the LMP is NP-hard; unlike the discrete TSP, however, the LMP has
defied efforts to achieve exact solutions, due to its combination of
combinatorial complexity with continuous geometry.
  We provide a number of new contributions that provide insights into the
involved difficulties, as well as positive results that enable both theoretical
and practical progress. (1) We show that the LMP is algebraically hard: it is
not solvable by radicals over the field of rationals, even for the simple case
in which $P$ is a $2\times 2$ square. This implies that it is impossible to
compute exact optimal solutions under models of computation that rely on
elementary arithmetic operations and the extraction of $k$th roots, and
explains the perceived practical difficulty. (2) We exploit this algebraic
analysis for the natural class of polygons with axis-parallel edges and integer
vertices (i.e., polyominoes), highlighting the relevance of turn-cost
minimization for Lawn Mowing tours, and leading to a general construction
method for feasible tours. (3) We show that this construction method achieves
theoretical worst-case guarantees that improve previous approximation factors
for polyominoes. (4) We demonstrate the practical usefulness \emph{beyond
polyominoes} by performing an extensive practical study on a spectrum of more
general benchmark polygons: We obtain solutions that are better than the
previous best values by Fekete et al., for instance sizes up to $20$ times
larger.

Computational Geometry