From:dillenco@baltic.ics.uci.edu (Michael Dillencourt)Date:1 Dec 1996 05:24:54 GMTNewsgroups:comp.theorySubject:Re: Traveling Salesman Problem and Delaunay Graphs

Recently, Michael I. Shamos posted the following message: In a recent post, Walter Schmitting asserts that my 1978 Ph.D. thesis on Computational Geometry contains the conjecture that a Euclidean traveling salesman tour is a subgraph of the Voronoi dual. This conjecture appears nowhere in the thesis, nor in any other of my published writings. I can confirm that I did indeed conjecture, for a period of about three weeks, that the stated result was true. A counterexample was shown to me by Richard Karp during a visit of his to CMU in 1977, long before the result of Kantabutra and Dillencourt. The conjecture appeared for a brief time in my unpublished notes entitled "Problems in Computational Geometry." As I was not a referee of the Kantabutra-Dillencourt paper, I was unable to correct any misimpression it may have given. I have exchanged several email messages with Dr. Shamos since he posted this message. I have also checked my earlier papers and Kantabutra's paper. I think at this point we can all agree that Dr. Shamos is right, he never published a conjecture of this result, and neither Kantabutra nor I ever claimed he did. (There never was a joint Kantabutra-Dillencourt paper.) This question of whether the Voronoi dual of a set of points necessarily contained the Euclidean traveling salesman cycle was listed as an open problem in Dr. Shamos' PhD thesis (page 206, #6). Dr. Shamos told me that Prof. Karp showed him the counterexample after his thesis had been submitted to University Microfilms, which is where I got my copy. I was curious about the 1977 counterexample. Dr. Shamos did not recall the details, and Prof. Karp did not remember either discussing the problem or solving it. Dr. Shamos said that he discussed the question with Prof. Karp, who showed him how to construct a counterexample and (most likely) promptly forgot about it. I can easily believe that this could have happened. At one point in my email exchange with Dr. Shamos, I erroneously interpreted one of his statements to imply that Prof. Karp had shown him a 4-point counterexample. Dr. Shamos later clarified this in a subsequent message, but in the meantime I thought about the problem and realized there is a 5-point counterexample. This is better than the 7-point counterexample in my 1985 paper [IPL 24(5), March 1987, 339-342]. This may or may not have been the same example Prof. Karp discovered in 1977, but in any case I thought it might be useful to describe it here. So now, finally, we get to the real point of this post, which is to describe a 5-point example of a Delaunay triangulation that does not contain the Euclidean Traveling Salesman Cycle (ETSC) as a subgraph. This is the smallest such example. The counterexample can be constructed as follows. Take four cocircular points A,B,C,D, in that order about a circle. Choose a fifth point E, outside the circle, chosen so that the convex hull of the five points is the triangle ADE and so that C is very close to the edge DE. If E is far enough outside the circle, and if the other four points are chosen appropriately, one can force the ETSC to be the cycle ABDCEA. If B is perturbed by a tiny amount and moved just outside the circumcircle of ACD, then edge BD will not be in the Delaunay triangulation. Rather than work out appropriate point locations analytically, I ran an experiment. I generated four random points on a unit circle (choosing theta uniformly), and then generated a fifth point randomly outside the unit circle and inside a circle of radius 8 (choosing theta uniformly, and choosing the radius uniformly in the range [1,8]). Out of 100,000 iterations, 2709 (2.7%) of the configurations generated were such that the ETSC contained one of the chords of the four cocircular points (BD in the terminology of the preceding paragraph, after relabeling). In each such case, if one of the endpoints of the chord is moved slightly so it is just outside the circle, the Delaunay triangulation will not contain the chord. There does not exist a four-point counterexample, if we disallow the trivial case of a totally collinear point set. Given any planar set of four points, either the points are in convex position (and the ETSC is the convex hull, which is a subgraph of the Delaunay triangulation) or the Delaunay triangulation is the complete graph. As I mentioned above, the example in my 1985 paper contained seven points, so it was not minimal. That example also was the minimum-weight triangulation of its vertex set. I don't know whether the construction sketched above can be used to construct a 5-point Delaunay triangulation that is also a minimum-weight triangulation and does not contain the ETSC. I'll post a picture of a specific 5-point example on my web site in the next week or so. ============================================================================= Michael B. Dillencourt Telephone: (714)-824-7556 Dept. of Info. and Computer Science Fax: (714)-824-4056 Computer Science Bldg. Email: dillenco@ics.uci.edu University of California WWW: http://www.ics.uci.edu/~dillenco Irvine, CA 92697-3425

From:Hoey@AIC.NRL.Navy.Mil (Dan Hoey)Date:05 Dec 1996 20:07:35 -0500Newsgroups:comp.theorySubject:Re: Traveling Salesman Problem and Delaunay Graphs

dillenco@baltic.ics.uci.edu (Michael Dillencourt) writes: > So now, finally, we get to the real point of this post, which is to > describe a 5-point example of a Delaunay triangulation that does not > contain the Euclidean Traveling Salesman Cycle (ETSC) as a subgraph. I'm not sure I understand your construction, but the following is a small 5-point example: ,C (5,2) (4,1) ,'/ ,,,,B / ,,,,---'''' / A---E-----------D (4,0) (0,0) (1,0) The minimum Euclidean circuit is ABCDE, but edge AB does not appear in the Delaunay triangulation (EC does). Dan Hoey Hoey@AIC.NRL.Navy.Mil