AbstractIn TSP with neighborhoods (TSPN) we are given a collection X of k polygonal regions in the plane, called neighborhoods, with totally n vertices, and we seek the shortest tour that visits each neighborhood. In this paper we present a simple and fast algorithm that, given a start point, computes a TSPN tour of length O(log k) times the optimum in time O(n+k log k). When no start point is given we show how to compute a "good" start point in time O(n2 log n), hence we obtain a logarithmic approximation algorithm that runs in time O(n2 log n). We also present an algorithm which performs at least one of the following two tasks (which of these tasks is performed depends on the given input):
(1) It outputs in time O(n log n) a TSPN tour of length O(log k) times the optimum.
(2) It outputs a TSPN tour of length less than (1+epsilon) times the optimum in time O(n3), where epsilon is an arbitrary real constant given as an optional parameter.
The same approach can be used for the Red-Blue Separation Problem. We show an algorithm with logarithmic approximation ratio that runs in time O(n log n), where n is the total number of points.
Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems; I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling
Additional Key Words and Phrases: computational geometry, approximation algorithms, red-blue separation, TSP with neighborhoods
Selected references
- Esther M. Arkin, Samir Khuller, and Joseph S. B. Mitchell. Geometric knapsack problems. Algorithmica, 10:399-427, 1993.
- Sanjeev Arora. Nearly linear time approximation schemes for Euclidean TSP and other geometric problems. In 38th Annual Symposium on Foundations of Computer Science, pages 554-563, Miami Beach, Florida, 20-22 October 1997. IEEE.
- M. R. Garey, R. L. Graham, and D. S. Johnson. Some NP-complete geometric problems. In Conference Record of the Eighth Annual ACM Symposium on Theory of Computing, pages 10-22, Hershey, Pennsylvania, 3-5 May 1976.
- John Hershberger and Subhash Suri. A pedestrian approach to ray shooting: Shoot a ray, take a walk. Journal of Algorithms, 18(3):403-431, May 1995.
- Christos H. Papadimitriou. The Euclidean Traveling Salesman Problem is NP-complete. Theoretical Computer Science, 4(3):237-244, June 1977.