Chadha, RituAllison, Donald C. S.2013-06-192013-06-191988http://hdl.handle.net/10919/19385We discuss a new heuristic for solving the Euclidean Traveling Salesman Problem (ETSP). This heuristic is a convex hull-based method and makes use of the Delaunay triangulation of the set of cities to compute a tour for the given set of cities. We conjecture that the expected running time for this algorithm is O(N log N), implying that a new and faster ETSP heuristic is now available.application/pdfenIn CopyrightTechnical reportTR-88-16http://eprints.cs.vt.edu/archive/00000101/01/TR-88-16.pdf