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”, SIAM Journal on Computing, volume 35, number 3, 2005, pages 531–566.
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 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.
- This paper is also available from SIAM. This paper is also available as arXiv:cs.DS/0309014 of the Computing Research Repository (CoRR).
- The paper is 36 pages.
- The paper is available in PDF (319k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- SODA2001a (Optimal Covering Tours with Turn Costs)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated August 3, 2020 by