On the Spacefilling Curve Heuristic for the Euclidean Traveling Salesman Problem

Bartholdi and Platzman [3] proposed the spacefilling curve heuristic for the Euclidean Traveling Salesman Problem and proved that their heuristic returns a tour within an O(lg n) factor of optimal length. They conjectured that the worst-case ratio is in fact O(1). In this note we exhibit a counterexample showing the O(lg n) upper bound is tight. This research is partially supported by the National Science Foundation under grant ECS8717970. y This material is based upon work supported under a National Science Foundation Graduate Fellowship. 1 Introduction Bartholdi and Platzman [3] proposed a heuristic for the Euclidean Traveling Salesman Problem (ETSP) based on a spacefilling curve. Their curve OE is a uniformly continuous map from the unit interval to the unit square. For our purposes we define OE as a total linear ordering ! OE on the points of the unit square [0; 1] 2 . This ordering may be defined by a recursive procedure; for any two distinct points (x; y) and (x 0 ; ..