AbstractIn TSP with neighborhoods (TSPN) we are given a collection

Xofkpolygonal regions in the plane, calledneighborhoods, with totallynvertices, 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(logk) times the optimum in time O(n+klogk). When no start point is given we show how to compute a "good" start point in time O(n^{2}logn), hence we obtain a logarithmic approximation algorithm that runs in time O(n^{2}logn). 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(

nlogn) a TSPN tour of length O(logk) times the optimum.(2) It outputs a TSPN tour of length less than (1+

epsilon) times the optimum in time O(n^{3}), whereepsilonis 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(

nlogn), wherenis 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.