Newsgroups: comp.theory
From: Hoey@AIC.NRL.Navy.Mil (Dan Hoey)
Date: 1996/12/05
Subject: Re: Traveling Salesman Problem and Delaunay Graphs

dille...@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