Testing the necklace condition for shortest tours and optimal factors in the plane
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.
Download (ext.)
Journal Article
| Published
| English
Scopus indexed
Author
Edelsbrunner, HerbertISTA 
;
Rote, Günter;
Welzl, Emo
;
Rote, Günter;
Welzl, EmoAbstract
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
Publisher
Elsevier
Volume
66
Issue
2
Page
157 - 180
ISSN
eISSN
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. Elsevier. 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. Elsevier, 1989. 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. Elsevier, 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.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level
Open Access
Google Scholar