Optimal Covering Tours with Turn Costs

Simple item page
dc.creatorArkin, Esther M.
dc.creatorBender, Michael A.
dc.creatorDemaine, Erik D.
dc.creatorFekete, Sandor P.
dc.creatorMitchell, Joseph S. B.
dc.creatorSethia, Saurabh
dc.date2003-09-09
dc.date2005-06-21
dc.date.accessioned2026-07-07T03:20:18Z
dc.date.available2026-07-07T03:20:18Z
dc.descriptionWe 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 em 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.
dc.description36 pages, 19 figures, 2 tables, Latex; to appear in SIAM Journal on Computing. New version contains more technical details in Sections 4.1, 5.1, 5.2, 5.5, four more figures, four more pages, as well as numerous smaller changes
dc.identifierhttps://arxiv.org/abs/cs/0309014
dc.identifierhttp://arxiv.org/abs/cs/0309014
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/31779
dc.subjectData Structures and Algorithms
dc.subjectComputational Geometry
dc.subjectF.2.2
dc.titleOptimal Covering Tours with Turn Costs
dc.typetext

Files

Collections

arXiv