Testing the necklace condition for shortest tours and optimal factors in the plane

H. Edelsbrunner, G. Rote, E. Welzl, Theoretical Computer Science 66 (1989) 157–180.

Download
No fulltext has been uploaded. References only!

Journal Article | Published
Author
; ;
Abstract
A tour of a finite set P of points is a necklace-tour if there are disks with the points in P as centers such that two disks intersect if and only if their centers are adjacent in . It has been observed by Sanders that a necklace-tour is an optimal traveling salesman tour. In this paper, we present an algorithm that either reports that no necklace-tour exists or outputs a necklace-tour of a given set of n points in O(n2 log n) time. If a tour is given, then we can test in O(n2) time whether or not this tour is a necklace-tour. Both algorithms can be generalized to ƒ-factors of point sets in the plane. The complexity results rely on a combinatorial analysis of certain intersection graphs of disks defined for finite sets of points in the plane.
Publishing Year
Date Published
1989-08-01
Journal Title
Theoretical Computer Science
Volume
66
Issue
2
Page
157 - 180
IST-REx-ID

Cite this

Edelsbrunner H, Rote G, Welzl E. Testing the necklace condition for shortest tours and optimal factors in the plane. Theoretical Computer Science. 1989;66(2):157-180. doi:10.1016/0304-3975(89)90133-3
Edelsbrunner, H., Rote, G., & Welzl, E. (1989). Testing the necklace condition for shortest tours and optimal factors in the plane. Theoretical Computer Science, 66(2), 157–180. https://doi.org/10.1016/0304-3975(89)90133-3
Edelsbrunner, Herbert, Günter Rote, and Emo Welzl. “Testing the Necklace Condition for Shortest Tours and Optimal Factors in the Plane.” Theoretical Computer Science 66, no. 2 (1989): 157–80. https://doi.org/10.1016/0304-3975(89)90133-3.
H. Edelsbrunner, G. Rote, and E. Welzl, “Testing the necklace condition for shortest tours and optimal factors in the plane,” Theoretical Computer Science, vol. 66, no. 2, pp. 157–180, 1989.
Edelsbrunner H, Rote G, Welzl E. 1989. Testing the necklace condition for shortest tours and optimal factors in the plane. Theoretical Computer Science. 66(2), 157–180.
Edelsbrunner, Herbert, et al. “Testing the Necklace Condition for Shortest Tours and Optimal Factors in the Plane.” Theoretical Computer Science, vol. 66, no. 2, Elsevier, 1989, pp. 157–80, doi:10.1016/0304-3975(89)90133-3.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar