Optimal Covering Tours with Turn Costs
Preprint
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 em 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 14 references indexed in Scilit:
- Optimization Problems Related to Zigzag Pocket MachiningAlgorithmica, 2000
- Improved lower bounds for the link length of rectilinear spanning paths in gridsInformation Processing Letters, 1998
- Angle-Restricted Tours in the planeComputational Geometry, 1997
- Minimal link visibility paths inside a simple polygonComputational Geometry, 1993
- L 1 shortest paths among polygonal obstacles in the planeAlgorithmica, 1992
- Watchman routes under limited visibilityComputational Geometry, 1992
- Triangulating a simple polygon in linear timeDiscrete & Computational Geometry, 1991
- Approximation algorithms for hitting objects with straight linesDiscrete Applied Mathematics, 1991
- Orthogonally convex coverings of orthogonal polygons without holesJournal of Computer and System Sciences, 1989
- Deterministic and probabilistic algorithms for maximum bipartite matching via fast matrix multiplicationInformation Processing Letters, 1981