@inproceedings{f2d09a33113d4b3582fb65c11a35d036,
title = "Optimal covering tours with turn costs",
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 not only on the length of the tour but also 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 lower bounds (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 = "Approximation algorithms, Covering, Lawn mowing, M-guillotine subdivisions, Manufacturing, Milling, NC machining, NP-completeness, Polynomial-time approximation scheme (PTAS), Traveling salesman problem (TSP), Turn costs",
author = "Arkin, \{Esther M.\} and Bender, \{Michael A.\} and Demaine, \{Erik D.\} and Fekete, \{S{\'a}ndor P.\} and Mitchell, \{Joseph S.B.\} and Saurabh Sethia",
year = "2001",
language = "English",
isbn = "0898714907",
series = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",
pages = "138--147",
booktitle = "Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms",
note = "2001 Operating Section Proceedings, American Gas Association ; Conference date: 30-04-2001 Through 01-05-2001",
}