Computer Science – Data Structures and Algorithms
Scientific paper
2003-09-09
Computer Science
Data Structures and Algorithms
36 pages, 19 figures, 2 tables, Latex; to appear in SIAM Journal on Computing. New version contains more technical details in
Scientific paper
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.
Arkin Esther M.
Bender Michael A.
Demaine Erik D.
Fekete Sandor P.
Mitchell Joseph S. B.
No associations
LandOfFree
Optimal Covering Tours with Turn Costs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Optimal Covering Tours with Turn Costs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimal Covering Tours with Turn Costs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-348766