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.
Users
Please
log in to take part in the discussion (add own reviews or comments).