direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 674-2000

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

Optimal Covering Tours with Turn Costs
Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Sándor P. Fekete, Joseph S. B. Mitchell, and Saurabh Sethia
A 10-page extended abstract is to appear in the proceedings of SODA '01
primary: 90C27 Combinatorial optimization
secondary: 68U05 Computer graphics; computational geometry
NC machining, manufacturing, traveling salesman problem, milling, lawn mowing, covering, approximation algorithms, polynomial-time approximation scheme, m-guillotine subdivisions, NP-completeness, turn costs.
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 report may be requested from our secretary Gabriele Klink, email: klink@math.tu-berlin.de
Title: Source

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe