This thesis contains the paper The N-line traveling salesman problem and an extension of the paper Testing the necklace condition for shortest tours and optimal factors in the plane, written jointly with Herbert Edelsbrunner and Emo Welzl. The improvement of the latter part has not been published elsewhere.
The other solvable case concerns the necklace condition: A tour is a necklace tour if we can draw disks with the given points as centers such that two disks intersect if and only if the corresponding points are adjacent on the tour. If a necklace tour exists, it is the unique optimal tour. We give an algorithm which tests in O(n3/2) time whether a given tour is a necklace tour, improving an algorithm of Edelsbrunner, Rote, and Welzl (1988) which takes O(n2) time. It is based on solving a system of linear inequalities by the generalized nested dissection procedure of Lipton, Rose, and Tarjan (1979). We describe how this method can be implemented with only linear storage. We give another algorithm which tests in O(n2 log n) time and linear space, whether a necklace tour exists for a given point set, by transforming the problem to a fractional 2-factor problem on a sparse bipartite graph. Both algorithms also compute radii for the disks realizing the necklace tour.