Approximation algorithms for lawn mowing and milling

We study the problem of finding shortest tours/paths for "lawn mowing" and "milling" problems: Given a region in the plane, and given the shape of a " cutter" (typically, a circle or a square), find a shortest tour/path for th e cutter such that every point within the region is covered by the cutter a t some position along the tour/path. In the milling version of the problem, the cutter is constrained to stay within the region. The milling problem a rises naturally in the area of automatic tool path generation for NC pocket machining. The lawn mowing problem arises in optical inspection, spray pai nting, and optimal search planning. Both problems are NP-hard in general. We give efficient constant-factor app roximation algorithms for both problems. In particular, we give a (3 + epsi lon)-approximation algorithm for the lawn mowing problem and a 2.5-approxim ation algorithm for the milling problem. Furthermore, we give a simple 6/5- approximation algorithm for the TSP problem in simple grid graphs, which le ads to an 11/5-approximation algorithm for milling simple rectilinear polyg ons, (C) 2000 Elsevier Science B.V. All rights reserved.