  For a given polygonal region $P$, the Lawn Mowing Problem (LMP) asks for a
shortest tour $T$ that gets within Euclidean distance 1 of every point in $P$;
this is equivalent to computing a shortest tour for a unit-disk cutter $C$ that
covers all of $P$. As a geometric optimization problem of natural practical and
theoretical importance, the LMP generalizes and combines several notoriously
difficult problems, including minimum covering by disks, the Traveling Salesman
Problem with neighborhoods (TSPN), and the Art Gallery Problem (AGP).
  In this paper, we conduct the first study of the Lawn Mowing Problem with a
focus on practical computation of near-optimal solutions. We provide new
theoretical insights: Optimal solutions are polygonal paths with a bounded
number of vertices, allowing a restriction to straight-line solutions; on the
other hand, there can be relatively simple instances for which optimal
solutions require a large class of irrational coordinates. On the practical
side, we present a primal-dual approach with provable convergence properties
based on solving a special case of the TSPN restricted to witness sets. In each
iteration, this establishes both a valid solution and a valid lower bound, and
thereby a bound on the remaining optimality gap. As we demonstrate in an
extensive computational study, this allows us to achieve provably optimal and
near-optimal solutions for a large spectrum of benchmark instances with up to
2000 vertices.
