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 \mathrm{\mid }S\mathrm{\mid }\mathrm{/}\log \log \mathrm{\mid }S\mathrm{\mid }}$ times the length of the shortest path visiting each element in $S$. ($C>0$ is a constant that depends only on the linear order.) This improves the previous lower bound $\ge C\sqrt[6]{\log \mathrm{\mid }S\mathrm{\mid }\mathrm{/}\log \log \mathrm{\mid }S\mathrm{\mid }}$ of [HKL06]. 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.