From: dillenco@baltic.ics.uci.edu (Michael Dillencourt)
Date: 1 Dec 1996 05:24:54 GMT
Newsgroups: comp.theory
Subject: 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 -0500
Newsgroups: comp.theory
Subject: 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