The travelling salesman problem (TSP) is well-known, see e.g. https://en.wikipedia.org/wiki/Travelling_salesman_problem.

Let us consider the Euclidean version of the TSP within the unit square. This means the metric is Euclidean and we only allow for cities within $[0,1]^2$.

The question I am interested in is: What are the worst cases of city positions with respect to the optimal solution of the TSP? I am interested in both, asymptotic results but also an algorithms that determine such sets (or sets, which are almost as bad as possible) for finite numbers of cities.

The length of an optimal TSP tour on a worst point set in $[0,1]^d$ with n points (let us call it $l^{(n)}$) is proven to be $\theta(n^{(d-1)/d})$ where $d$ is the dimension, so here, as we look at the two-dimensional unit square we have $l=\theta(n^{1/2})$. To see that there are such point sets where the optimal tour is $\Omega(n^{1/2})$ one can consider rectangular lattices. (See the paper of Snyder and Steele and references inthere.)

However, I am interested in how the point sets look like. Asymptoticlly, it might be intuitive to assume that the cities are somehow equidistributed. Indeed in the referenced paper of Snyder and Steele, they show that this is the case in the following sense:

For any $n \in \mathbb N$ let $S^{(n)}$ be a worst-case point set with $n$ points. Let $R \subseteq [0,1]^2$ be any rectangle in the unit square with area $A(R)$. Then the following conclusion holds: $ \lim\limits_{n \rightarrow \infty} \frac{1}{n} |S^{(n)} \cap R| = A(R)$.

Note that two years later they generalized this result to higher dimensions, using a different approach.

I have four questions:

- "How unique" are sets (or more precisely sequences of sets of increasing size, as we want to make asymptotical statements), that fulfill the "uniformness condition" of the conclusion of the theorem?
- Are there any algorithms known for the finite-case (i.e. non-asymptotical) which provide point-sets which are provably close to "worst-possible"?
- In the asymptotical case, is the reverse direction also true in the sense, that every sequence of sets of increasing size that fulfills the "uniformness condition" of the theorem is also asymptotically worst-case? This is related with 1.
- More general, what are further references to this topic. What has been found since the paper from Snyder and Steele which is from 1993?

Thanks in advance!

*Timothy Law Snyder and J. Michael Steele*, MR 1213258 **Equidistribution of point sets for the traveling salesman and related problems**, *Proceedings of the {F}ourth {A}nnual {ACM}-{SIAM} {S}ymposium on {D}iscrete {A}lgorithms ({A}ustin, {TX}, 1993)* (1993), 462--466.