Paper by Erik D. Demaine
- Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Sándor P. Fekete, Joseph S. B. Mitchell, and Saurabh Sethia, “Optimal Covering Tours with Turn Costs”, in Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2001), Washington, DC, January 7–9, 2001, pages 138–147.
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.
- The paper is 10 pages.
- The paper is available in PostScript (253k) and gzipped PostScript (89k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- Milling (Optimal Covering Tours with Turn Costs)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated November 6, 2023 by