MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

5 used right definition of area (and not my intuitive one which was off by a factor of n)

You should be able to get $O(\sqrt{n/k})$ by choosing a smaller square of area $k/n$, 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/n$, /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 n/k$ /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})$. 4 added 399 characters in body; added 7 characters in body; deleted 21 characters in body; added 14 characters in body; added 1 characters in body If you're fixing Here's a strategy for a proof of$k$and letting O(\sqrt{n/k})$. First take a square of area $n$ go to \alpha k/n$, with$\infty$, \alpha$ chosen so that this contains $9/10\, n$ of the asymptotic behavior is going to go like classes of points. The BHH theorem shows you can find a TSP tour of this square with length $O(f(k)\sqrt{n})$ for some function 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$k$. It seems like S_1$, $S_2$, $S_3$, $\ldots$, $S_{\log n}$ where the real question $i$'th square is then: what big enough that the expected number of classes of points it contains is $f(k)$. (1-1/10^{i})n$. The reasoning above shows that$f(k)$grows at least like area of the$1/\sqrt{k}$. And it's quite clear that i$'th square will be $f(k)$ is at most \alpha i n/k$for some constant$1$(choose \alpha$. To get a point randomly from each set, and use TSP of the BHH theorem)$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})$.

3 added 388 characters in body

You should be able to get $O(\sqrt{n/k})$ by choosing a smaller square of area $k/n$, 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})$.

If you're fixing $k$ and letting $n$ go to $\infty$, the asymptotic behavior is going to go like $O(f(k)\sqrt{n})$ for some function of $k$. It seems like the real question is then: what is $f(k)$. The reasoning above shows that $f(k)$ grows at least like $1/\sqrt{k}$. And it's quite clear that $f(k)$ is at most $1$ (choose a point randomly from each set, and use the BHH theorem).

2 added 112 characters in body
1