Lower bounds for the universal TSP on the plane

We show a lower bound for the universal traveling salesman heuristic on the plane: for any linear order on the unit square \([0, 1]^2\), there are finite subsets \(S \subset [0, 1]^2\) of arbitrarily large size such that the path visiting each element of \(S\) according to the linear order has length \(\ge C \sqrt{ \log |S| \log \log |S|}\) times the length of the shortest path visiting each element in \(S.\) (\(C \gt 0\) is a constant that depends only on the linear order.) This improves the previous lower bound \(\ge C\ ^6 \!\!\!\!\sqrt{ \log |S| \log \log |S|}\) of Hajiaghayi, Kleinberg and Leighton (SODA 2006). The proof establishes a dichotomy about any long walk on a cycle: the walk either zig-zags between two far away points, or else for a large amount of time it stays inside a set of small diameter.