Approximation algorithms for lawn mowing and milling

Arkin, Esther M. and Fekete, Sandor P. and Mitchell, Joseph S. B. (2000) Approximation algorithms for lawn mowing and milling.
Published in: Computational geometry : theory and applications Vol. 17 (1-2). pp. 25-50.


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 the cutter such that every point within the region is covered by the cutter at 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 arises naturally in the area of automatic tool path generation for NC pocket machining. The lawn mowing problem arises in optical inspection, spray painting, and optimal search planning. Both problems are NP-hard in general. We give efficient constant-factor approximation algorithms for both problems. In particular, we give a (3+epsilon)-approximation algorithm for the lawn mowing problem and a 2.5-approximation algorithm for the milling problem. Furthermore, we give a simple 6/5-approximation algorithm for the TSP problem in simple grid graphs, which leads to an 11/5-approximation algorithm for milling simple rectilinear polygons.

Download: [img] Postscript - Preprinted Version
Download (1MB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr97-255
Depositing User: Archive Admin
Date Deposited: 02 Apr 2001 00:00
Last Modified: 16 Jan 2012 13:29