Approximation algorithms for planar traveling salesman tours and minimum-length triangulations
Kenneth L. Clarkson · 1991
This paper gives a partitioning scheme for the geometric, planar traveling salesman problem, under the Euclidean metric: given a set S of n points in the plane, find a shortest closed tour (path) visiting all the points. The scheme employs randomization, and gives a tour that can be expected to be short, if S satisfies the condition that a random subset R ae S has on average a tour much shorter than an optimal tour of S. This condition holds for points independently, identically distributed in the plane, for example, for which a tour within 1 + ffl of shortest can be found in expected time nk 2 2 k , where k = O(log log n) 3 =ffl 2 . One algorithm employed in the scheme is of interest in its own right: when given a simple polygon P , it finds a Steiner triangulation of the interior of P . If P has n sides and perimeter LP , the edges of the triangulation have total length LP O(log n). If this algorithm is applied to a simple polygon induced by a minimum spanning tree of a poi...