It is proved that there are constants $c_{1}$, $c_{2}$, and $c_{3}$ such that for any set S of n points in the unit square and for any minimum-length tour T of S the sum of squares of the edge lengths of T is bounded by $c_{1} \log n$. (2) the number of edges having length t or greater in T is at most $c_{2}/t^{2}$, and (3) the sum of edge lengths of any subset E of T is bounded by $c_{3}|E|^{1/2}$. The second and third bounds are independent of the number of points in S, as well as their locations. Extensions to dimensions $d > 2$ are also sketched. The presence of the logarithmic term in (1) is engaging because such a term is not needed in the case of the minimum spanning tree and several analogous problems, and, furthermore, we know that there always exists some tour of S (which perhaps does not have minimal length) for which the sum of squared edges is bounded independently of n.

Given a set S of n points in the unit square $[ 0,1 ]^d $, an optimal traveling salesman tour of S is a tour of S that is of minimum length. A worst-case point set for the traveling salesman problem in the unit square is a point set $S^{( n )} $ whose optimal traveling salesman tour achieves the maximum possible length among all point sets $S \subset [ 0,1 ]^d $, where $| S | = n$. An open problem is to determine the structure of $S^{( n )} $ We show that for any rectangular parallelepiped R contained in $[ 0,1 ]^d $, the number of points in $S^{( n )} \cap R$ is asymptotic to n times the volume of R. Analogous results are proved for the minimum spanning tree, minimum-weight matching, and rectilinear Steiner minimum tree. These equidistribution theorems are the first results concerning the structure of worst-case point sets like $S^{( n )} $.

The tour given by the spacefilling curve heuristic applied to a random sample of points from the unit square differs in subtle ways from the shortest tour through those points. In particular, the expected length of the heuristic tour is found to be asymptotic to √n times a periodic function of log n for a broad class of spacefilling curves. The theory is developed further by detailing the self-similarity properties of the spacefilling curve that are useful for obtaining the asymptotics of the expected length of the heuristic path. Finally, the theory of martingales is applied to obtain tail bounds that yield rigorous almost sure asymptotics for the length of the heuristic tours.

The sum of squares of the edge lengths of the tour provided by the spacefilling curve heuristic applied to a random sample of n points from the unit square is proved to be asymptotically equal to a periodic function of the logarithm of the sample size.

It is proved that there are constants c1, c2, and c3 such that for any set S of n points in the unit square and for any minimum-lengths of T of S (1) the sum of squares of the edge lengths of T is bounded by c1 log n, (2) the sum of edge lengths of any subset E of T is bounded by c2|E|1/2, and (3) the number of edges having length t or greater in T is at most c3/t2. The second and third bounds are independent of the number of points in S, as well as their locations. Extensions to dimensions d>2 are also sketched.The presence of the logarithmic term in (1) is engaging because such a term is not needed in the case of the minimum spanning tree and several analogous problems, and, furthermore, we know that there always exists some tour of S (which perhaps does not have minimal length) for which the sum of squared edges is bounded independently of n.

Abstract The worst‐case behavior of greedy matchings of n points in the unit d‐cube, where d ≥ 2, is analyzed. The weighting function is taken to be the α'th power of Euclidean distance, where 0 < α < d. It is proved that the asymptotic growth rate of the weight of such a greedy matching is exactly βn(d‐α)/d, where β is a positive constant that depends on the parameters α and d. Included in the analysis is a minimax theorem equating the worstcase behaviors of matchings resulting from greedy algorithms that, when ordering edges for the greedy process, break ties in different ways.

A method is presented for determining the asymptotic worst-case behavior of quantities like the length of the minimal spanning tree or the length of an optimal traveling salesman tour of n points in the unit d-cube. In each of these classical problems, the worst-case lengths are proved to have the exact asymptotic growth rate of $\beta _n^{{{(d - 1)} / d}} $, where $\beta $ is a positive constant depending on the problem and the dimension. These results complement known results on the growth rates for the analogous quantities under probabilistic assumptions on the points, but the results given here are free of any probabilistic hypotheses.

An algorithm is given which makes only $O(\log n)$ comparisons, and which will determine the ordering of the uniformly distributed (pseudo random) Weyl sequences given by $\{ (k\alpha )\bmod 1:1 \leqq k \leqq n\} $, where $\alpha $ is an unspecified irrational number. This result is shown to be best possible in the sense that no algorithm can perform the same task with fewer than $ \Omega (\log n)$ comparisons.