Optimal covering tours with turn costs

Esther M. Arkin; Michael A. Bender; Erik D. Demaine; Sándor P. Fekete; Joseph S.B. Mitchell; Saurabh Sethia

doi:10.1137/S0097539703434267

Optimal covering tours with turn costs

Esther M. Arkin
, Michael A. Bender
, Erik D. Demaine
, Sándor P. Fekete
, Joseph S.B. Mitchell
, Saurabh Sethia

Massachusetts Institute of Technology
Technical University of Braunschweig
SoftJin Infotech Pvt. Ltd.

Research output: Contribution to journal › Article › peer-review

78 Scopus citations

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 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 polynomialtime approximation scheme based on a novel adaptation of the m-guillotine method.

Original language	English
Pages (from-to)	531-566
Number of pages	36
Journal	SIAM Journal on Computing
Volume	35
Issue number	3
DOIs	https://doi.org/10.1137/S0097539703434267
State	Published - 2005

Keywords

Approximation algorithms
Covering
Lawn mowing
M-guillotine subdivisions
Manufacturing
Milling
Nc machining
Np-completeness
Polynomial-time approximation scheme
Traveling salesman problem
Turn costs

Access to Document

10.1137/S0097539703434267

Cite this

@article{3276af69353e44259472f90dab6a00bf,

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 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 polynomialtime 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, Traveling salesman problem, 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 = "2005",

doi = "10.1137/S0097539703434267",

language = "English",

volume = "35",

pages = "531--566",

journal = "SIAM Journal on Computing",

issn = "0097-5397",

number = "3",

}

TY - JOUR

T1 - Optimal covering tours with turn costs

AU - Arkin, Esther M.

AU - Bender, Michael A.

AU - Demaine, Erik D.

AU - Fekete, Sándor P.

AU - Mitchell, Joseph S.B.

AU - Sethia, Saurabh

PY - 2005

Y1 - 2005

N2 - 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 polynomialtime approximation scheme based on a novel adaptation of the m-guillotine method.

AB - 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 polynomialtime approximation scheme based on a novel adaptation of the m-guillotine method.

KW - Approximation algorithms

KW - Covering

KW - Lawn mowing

KW - M-guillotine subdivisions

KW - Manufacturing

KW - Milling

KW - Nc machining

KW - Np-completeness

KW - Polynomial-time approximation scheme

KW - Traveling salesman problem

KW - Turn costs

UR - https://www.scopus.com/pages/publications/33745468623

U2 - 10.1137/S0097539703434267

DO - 10.1137/S0097539703434267

M3 - Article

AN - SCOPUS:33745468623

SN - 0097-5397

VL - 35

SP - 531

EP - 566

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 3

ER -

Optimal covering tours with turn costs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this