Optimal Covering Tours with Turn Costs: A Study in Geometric Traveling Salesman Problems

Title: Optimal Covering Tours with Turn Costs: A Study in Geometric Traveling Salesman Problems

Abstract: This research focuses on the geometric Traveling Salesman Problem, specifically addressing the covering tour problem. The objective is to find a polygonal tour for a cutter that minimizes turn costs, ensuring the cutter sweeps a specified region while avoiding gouging material outside the region. The study presents several key findings and contributions:

1. Proof of NP-completeness: The research team proves that the covering tour problem with turn costs is NP-complete, even when the objective is purely to minimize the number of turns, the pocket is orthogonal, and the cutter moves axis-parallel.

2. Constant-factor approximation algorithms: The study provides efficient algorithms that approximate the optimal tour with respect to turn costs in various problem versions. These algorithms are significant as they effectively solve the problem in most cases.

Implications of this research are far-reaching, affecting various fields such as manufacturing, automatic inspection, arc routing, and robotic exploration. The constant-factor approximation algorithms provide a practical solution to the problem, making the research valuable for industries and applications that require efficient and cost-effective covering tours.

Link to Article: https://arxiv.org/abs/0309014v2 Authors: arXiv ID: 0309014v2