Saurabh Sethia
Saurabh Sethia has a total of 5 co-authors. Here are the top co-authors by number of shared publications:
- Erik D. Demaine
Computer Science and Artificial Intelligence Laboratory, MIT, Cambridge, MA, USA
1 shared publication Esther M. Arkin
Department of Applied Mathematics and Statistics State University of New York 11794-3600 Stony Brook NY USA
1 shared publicationJoseph S. B. Mitchell
Department of Applied Mathematics and Statistics State University of New York 11794-3600 Stony Brook NY USA
1 shared publication- Michael A. Bender
Department of Computer Science, Stony Brook University, Stony Brook, USA
1 shared publication - Sandor P. Fekete
Department of Computer Science, TU Braunschweig, Braunschweig, Germany
1 shared publication
Latest Publications
- Open Access
Optimal Covering Tours with 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 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.
Open AccessOptimal Covering Tours with 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 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.