Optimal Covering Tours with Turn Costs
Authors:
- Esther M. ArkinEAEsther M. Arkin
- Michael A. BenderMBMichael A. Bender
- Erik D. DemaineEDErik D. Demaine
- Sándor P. FeketeSFSándor P. Fekete
- Joseph S. B. MitchellJMJoseph S. B. Mitchell
- Saurabh SethiaSSSaurabh Sethia
- 1 January 2005
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 35 (3) , 531-566
Abstract
We give the first algorithmic study of a class of "covering tour" problems related to the geometric traveling salesman problem: Find a polygonal tour for a cutter so that it sweeps out a specified region ("pocket") in order to minimize a cost that depends mainly on the number of turns. These problems arise naturally in manufacturing applications of computational geometry to automatic tool path generation and automatic inspection systems, as well as arc routing ("postman") problems with turn penalties. We prove the NP-completeness of minimum-turn milling and give efficient approximation algorithms for several natural versions of the problem, including a polynomial-time approximation scheme based on a novel adaptation of the m-guillotine method.Keywords
All Related Versions
This publication has 30 references indexed in Scilit:
- Minimum-link watchman toursInformation Processing Letters, 2003
- APPROXIMATION ALGORITHM FOR MULTIPLE-TOOL MILLINGInternational Journal of Computational Geometry & Applications, 2001
- Approximation algorithms for lawn mowing and milling☆☆A preliminary version of this paper was entitled “The lawnmower problem” and appears in the Proc. 5th Canad. Conf. Comput. Geom., Waterloo, Canada, 1993, pp. 461–466.Computational Geometry, 2000
- Optimization Problems Related to Zigzag Pocket MachiningAlgorithmica, 2000
- The Directed Rural Postman Problem with Turn PenaltiesTransportation Science, 1999
- Improved lower bounds for the link length of rectilinear spanning paths in gridsInformation Processing Letters, 1998
- Finding an approximate minimum-link visibility path inside a simple polygonInformation Processing Letters, 1995
- Minimal link visibility paths inside a simple polygonComputational Geometry, 1993
- Triangulating a simple polygon in linear timeDiscrete & Computational Geometry, 1991
- Orthogonally convex coverings of orthogonal polygons without holesJournal of Computer and System Sciences, 1989