Generalized Euclidean TSP

Question

Suppose I have n sets $X_1,\dots,X_n$ consisting of $k$ points each, where all $nk$ points are i.i.d. uniform random samples in the unit square $[0,1]\times[0,1]$. Consider the shortest path that goes through at least one element of each set $X_i$. Is the asymptotic behavior of this, a la the Beardwood-Halton-Hammersley (BHH) theorem, well-known? (By "asymptotic behavior", I mean, assume that $k$ is fixed and look at what happens as $n$ becomes large)

Answer 1

You should be able to get $O(\sqrt{n/k})$ by choosing a smaller square of area $1/k$, which will contain one point from most of the point sets, and use the BHH theorem to find a TSP tour of this. Now, you have to show that adding the points from the point sets you left out doesn't increase the length of the tour much. It certainly won't increase it by more than a $\sqrt{\log n}$ factor, because a square $\log n$ times larger in area will with high probability contain a point from all the point sets, and choosing one point randomly from each of the point sets in that square gives points uniform in this square. I'd guess the tour length will still be $O(\sqrt{n/k})$, but you may have to do some work to prove this. On the other hand you certainly can't do better than this, because you need $n$ points in your tour, and the typical distance from one point to its nearest neighbor is $O(1/\sqrt{nk})$.

Here's a strategy for a proof of $O(\sqrt{n/k})$. First take a square of area $\alpha /k$, with $\alpha$ chosen so that this contains $9/10\, n $ of the classes of points. The BHH theorem shows you can find a TSP tour of this square with length $O(\sqrt{n/k})$. Now, we need to show adding the rest of the points doesn't increase the tour length very much.

We'll find subsquares $S_1$, $S_2$, $S_3$, $\ldots$, $S_{\log n}$ where the $i$'th square is big enough that the expected number of classes of points it contains is $(1-1/10^{i})n$. The area of the $i$'th square will be $\alpha i /k$ for some constant $\alpha$. To get a TSP of the $9/10^in$ new classes of points in the $i$'th square takes length $O\left(\sqrt{i 9/10^i n/k}\right)$. The series sums to $O(\sqrt{n/k})$.