Please see PDF version

Chapter 50
Equidistribution of Point Sets for the
Traveling Salesman and Related Problems

Timothy Law Snyder* J. Michael Steele**

Abstract . TSP(S) to denote the set of edges of an optimal travel
Given a set S of n points in the unit square [0, 1]2, ing salesman tour of S and iTSP(S)l to denote the sum

an optimal traveling salesman tour of S is a tour of of the Euclidean lengths of the edges in TSP(S).
S that is of minimum length. A worstcase point set A worstcase optimal traveling salesman tour is a
for the Traveling Salesman Problem in the unit square tour of total length
is a point set S(n) whose optimal traveling salesman PTSP(n) = max, ITSP(S)j. (1.1)
tour achieves the maximum possible length among all SC[0,1]
point sets S C [0, 112, where JS1 = n. An open problem ISI=n
is to determine the structure of S(n). We show that In words, PTS1(n) is the maximum length, over all point
foi any rectangle R contained in (0, 1]2, the number of sets in [0, 112 1 of size n, that an optimal traveling sales
points inS(n) n R is asymptotic to n times the area of man tour can attain. Such a tour attaining this length
R. One corollary of this result is an 0(n log n) approx is called a worstcase TSP tour and its associated point
imation algorithm for the worstcase Euelidean TSP.
Analogous results are proved for the rniinimum spanning set a worstcase TSP point set.
tree, minimurnweight matching, and rectilinear Steiner The first works on the sequence PTSP(n) were
minimum tree. These equidistribution theorems are the the lower bounds of FejesT6th (1940) and the up
first results concerning the structure of worstcase point per bounds of Verblunsky (1951). Successive improve
sets like S(n). ments to these bounds and their higherdimensional
analogues appeared in Few (1955), Supowit, Reingold,
1. Introduction and Plaisted (1983), Moran (1984), Goldstein and Rein
gold (1988), KarloIT (1989), and Goddyn (1990). One

This paper deals with worstcase arrangements of result we use later is that
points for problems in combinatorial optimization; it is
shown that these point sets are equidistributed. For liM PTSP(n)/n1/2 =,6T,P,
n co
specificity, we concentrate on the Traveling Salesman
Problem. where flTr., > 0 is a constant (Steele and Snyder (1989)).
Given a set of points S in the unit squaxe [0, 1]2, an All these results deal with the worstcase length
optimal traveling salesman tour of S is a tour consist PT51(n). There are no results, however, concerning the
ing of edges from the complete graph on S and having locations of the points that give rise to a worstcase
total length minrf jel : T is a tour of S }. Here, tour. Let S(n) be a worstcase TSP point set. An en
jel denotes the Euclidean length of the edge e. We use gaging open problem is to determine the structure of

Department of Computer Science, Georgetown University, Washington, DC 20057. Research supported in part by Georgetown University 1991 Summer Research Award and Georgetown University 1992 Junior Faculty Research Fellowship.

Department of Statistics, The Wharton School, University of Pennsylvania, Philadelphia, PA 19104. Research supported in part by the following grants: NSF DMS9211634, NSA MDA90489H2034, AFOSR890301, and ARO DAAL0391G0110.

1 1


S0'). It is generally believed that SK is asymptot and label the cells Qi, where 1 S i < M2, then, for all ically a lattice; for example, Supowit, Reingold, and 1 < i < M2,
Plaisted (1983) conjectured a hexagonal grid for S(n). JS(,0 n Qi 1 1
Our main result is that any sequence of wor~tcase lim (2.1)
TSP point sets is asymptotically equidistributed: noo n 2
Theorem 1. If { S(n) : 1 < n < oo } is a sequence Let s(n, i) = IS(n) n Qi J; in words, s(n, i) is the
of worstcase T5P point sets, then, for any rectangle number of points in the ith cell of a worstcue TSP
R C [0, 1]2, point set. Points that lie on the boundaxies of the Qi
can be arbitrarily assigned. Furthermore, let
liM 1 JS(n n R 1 = Area(R). (1.3) M2 rn 2
n co n 1
1/2 ~ ;~2 E {8(n, j)} 1 / 2
A corollary to Theorem 1 is that any worstcase Eu j=1
clidean traveling salesman problem can be solved within (2.2)
a factor of 1 + e, for any e > 0, in 0(n log n) time us One should note that if X is a random variable taking
ing the algorithm of Karp (1976). Even though Karp's on the value {s(n, j)}1/2 with probability 1/M2, then
algorithm is for points drawn uniformly from the unit V, is the variance of X. Our first lemma estimates the
square, we discuss in the concluding section how The expected value of X.
orem 1 and the limit (1.2) guarantee this performance Lemma 1. As n oo,
for worstcase point sets.
The proof of Theorem 1 rests on the limit (1.2) and M2 2 n1/2 112).
a characterization of ISK n R 1 in probabilistic terms. ;~2 DS( nJ)}l/ m + o(n (2.3)
Even though S(n) is deterministic, a simple probabilis j=1
tic identity plays a useful role. We show in a later sec Proof.
tion that the method provides analogous theorems for First write (1.2) as
other problems, including the minimum spanning tree,
minimum weight matching, and rectilinear Steiner tree. p,(n) = Onl/2 + r(n), where r(n) = o(nl/2); (2.4)
In Section 2, we begin with two observations that
simplify the proof of Theorem 1 in Section 3. Section 4 for convenience, we have dropped the "TSP" from,3Tsp.
contains results and proofs for problems other than the Let W denote a closed walk on S(n) = {X,, X2, . .. 1
Traveling Salesman Problem, and Section 5 concludes Xn}, Le, W. is a sequence of edges (Xi,, ,ni2), (~ri2, 2~i3),
with speculations on extensions and applications of our (xi,, , (xi,,, zi,) that visits each point of S(n)
results, including algorithmic ones. at least once and begins and ends at the same point.
Since W is feasible for the traveling salesman problem
2. Deviations from the Mean Number on S(n) even if W visits some points more than once
of Points per Cell and traverses some edges, more than once, F_,, e W 1 e 1 <
To prove Theorem 1, it suffices to show that if we We now construct a closed walk W on S(n) as fol
divide the unit square [0, 1]2 into M2 equallysized par lows. Label the cells Qi with the numbers 1 through
allel subsquares or cells, each having side length 1/m, M2 by traversing the cells row by row, proceeding left


to right in the first row, right to left in the second, and where h(n) = o(nl/2). This proves half of the
so on, alternating the direction of traversal in each row lemma. To obtain the other half, we note from the
until all cells have been labeled. Next, construct in each Schwarz inequality that E'21{s(n,i)}1/2 < rnnl/l
cell Qi an optimal traveling salesman tour of the points since E' 2 1 s(n, n.
of S(n) that lie in Qi. These disjoint, withincell tours
are then connected by placing an edge ei between cell

number i and cell number i + 1, for 1 < i < m2  1. We now use Lemma 1 and the characterization of
A closed walk W that traverses each of the withincell Vn as a variance to show that V,,/n goes to zero.
tours once and each of the ei twice can then be obtained.
To assess the length of W, let Qi and Qj be adja Lemma 2. For V,, as defined in Equation (2.2), we
cent cells. Since any pair of points in Qi U Qj can be have
connected by a line segment of length at Most 51/2/M, V,, = o(n) (2.8)

PTSP(n) = ITSP(S(n))l
< jel as n  oo.

M2 rn21 (2.5) ProoŁ

ITSP(S(n) n Qi) 1 + 2 lei 1
First note that V,, can be written as

< ITSP(S(.) n Qi) I + 2. 51/2m. M2 2
E 9(n, i)  ( L
m M, n,
We now use (2.4) in (2.5) along with the fact that j=1

iTSP(S(.) n Qi) I is at most PTSP(s(n, i)) scaled by the using the remark following definition (2.2) and the iden
cell size 1/m to get tity Var(X) = EX2  (EX)2. Since E,2 s(n, i) = n,
PTSP(n) =fln1/2 + r(n) applying Lemma 1 to the second term of (2.9) gives
< M > PTSP(s(n, i)) + 2. 51/2M V, = n _ (ni/2 + 0(ni/2) 2.
i=1 ;;72 m (2.10)
rn2 (2.6)
< 0{s(n, j)}1/2 On expanding, we see that Vn = o(n).

+ r(s(n, i)) + 2. 51/2m,

where, for all 1 < i < m2, the value r(s(n, ffl 3. Equidistribution in the Worst
o({s(n,i)}1/2) = 0(n112). Since m is fixed, we cancel Ca'se TSP
to find

j)}1/2 > rnn112 + h(n), (2.7) To prove Theorem 1, recall that it suffices to show
that lim,,, IS(n) n Qil/n = 1/M2, for all 1 S i < rn 2.

1 1


Jrom the definition (2.2) of V,,,we have that for all i For example, if L(S) = MST(S) denotes the to
satisfying 1 < i < M2, tal length of a minimum spanning tree of S, we first

rn2 form minimum spanning trees MST~S,,,, n Qi) on the
I{S(n,i)}1/2 1 1,2. ints of SM(%)T in the cells Qi, where 1 < i < m~. The
Y7{s(n, j)}1/21 :5 MV (3.1) P'
j=1 trees within cells can then be interconnected at total
cost 0(m) = o(nl/2) by adding M2  1 edges, each
Applying first Lerruna 2 then Lemma 1 to (3.1) gives costing no more than 51/2/M. This forms a heuris
tie tree on S,(,n.),. Since the lengths IMST( WTn Qi)l

{s(n, i)}1/2 2 nJ)}1/1 + o(nlll) are no greater than the worstcase (withincell) lengths
;~2 DS( M1PMST(SMST(n,i)), Condition 2 follows.
j=1 (3.2) Checking these conditions for each of the problems
n1/2 + o(nl/2). yields the following.
Theorem 2. If { S,(n) : 1 < n < w } is a sequence
Squaring (3.2) yields Theorem 1. of worstcase point sets for the function L, where L is
the mi 1 ni . mum spanning tree, the minimum matching,
or the rectilinear minimum Steiner tree, then, for any
4. Equidistribution in the MST, rectangle R C [0, 111,
1 IS(n
Matching, and Steiner Problems lim L ) n R Area(R). (4.1)
n oa n

The method just used for the TSP can be applied 5. Concluding Remarks

to the minimum spanning tree, the minimumlength The asymptotic equidistribution of worstcase point
matching, and the rectilinear minimum Steiner tree. sets for the problems we have considered ollers some
If L = L(S) denotes the length associated with any support to the conjectures of Supowit, Reingold, and
of these, then we can define p,(n) = sups:isl=, L(S) Plaisted (1983) that worstcase point sets are approxi
and let S( ) be such that L(S(L")) = PTSP(n). To show mated by lattices as n , oc. It is still a major open
that S(Ln) is asymptotically equidistributed boils down problem to resolve these conjo~ctures.
to checking that L satisfies two conditions: The results also prove that the worstcase travel
1. PL(n) = flLn1/2 + o(nl/2), where fl, > 0 is constant; ing salesman problem on S(n) is amenable to Karp's
2_ PL(n) < M_, + o(n'12), where probabilistic algorithm for the TSP, even though S(n) is
of S(n)
$,(n,i) is the number of points contained entirely deterministic. For n points selected uniformly
in the cell Qi. from [0, 1]2, Karp's algorithm runs in 0(n log n) time
with probability one, and, for all e > 0, the tour formed
Condition 1 has been proved for the minimum span by the algorithm. is within a factor of 1 + e of optimum
ning tree, minimum matching, and rectilinear Steiner with probability one, as n oo.
tree problems (cf., Steele and Snyder (1989) and Sny Using Karp's algorithm, given c > 0, we can guar
der (1992)), and Condition 2 can be verified for these antee the construction of a tour T of S(n) in 0(n log n)
problems by the method used in the proof of Lemma 1. time such that the total length of T is at most 1 + 6

times the optimal length PTIP(n), as n ~ oo. These re Hence, this problem also remains open.
sults are entirely deterministic, and they can be proved
by observing that Karp's analysis uses a probabilistic
counterpart to the limit theorem expressed by (1.2) References
along with asymptotic equidistribution of point sets
uniformly selected from the unit square. Though the
limit (1.2) for the worstcase length of the TSP has been FeJesT6th, L.T. (1940). "tber ein geometrische Satz,"
known for several years, an equidistribution result for Math. Zeit. 46, 299327.
S(n) was required in order to guarantee both the time Few, L. (1955). "The shortest path and the shortest
and performance bounds for Kaxp's algorithm applied
to S(n). Until there are definitive tests for worstcase road through n points in a region," Mathe
point sets, however, this result is only of theoretical in matika 2, 141144.
terest; whether it can be used for point sets other than Goddyn, L. (1990). "Quantizers and the worstcase Eu
S(n) is an open problem. clidean traveling salesman problem," J. Comb.
Several other open problems are motivated by our Theory, Series B 50, 65~81.
results. For any finite set of points S, the Steiner prob
lem is to find a rninimumlength tree T (V, E) such Karloff, H.J. (1989). "How long can a Euelidean tray
that V contains S. The added points Q V  S are eling salesman tour be?" SIAM J. Disc. Math.
the Steiner points of T. Though any metric can be used 2, 9199.
to assign costs to edges, two metrics of interest are the
Euclidean and rectilinear (L,). Karp, R.M. (1976). "The probabilistic analysis of
Let S0) be a worstcase point set for the rectilin some combinatorial search algorithms," in Al
ear Steiner problem, and let T be a rectilinear minimum gorith= and Complexity: New Directions and
Steiner tree of S(n). The asymptotic equidistribution in Recent Results, J.F. Traub, ed., Academic
theorem 2 applies only to S(n), and not to the set Q of Press, New York, 119.
Steiner points of T; we conjecture that Q is asymptoti Moran, S. (1984). . "On the length of optimal TSP cir
cally equidistributed, as well. cuits in sets of bounded diameter," J. Comb.
For the Euclidean Steiner problem, the limit result Theory, Series B 37, 113141,
for Condition 1 in Section 4 has yet to be established.
We believe such a result holds, and it would imply that a Snyder, T.L. (1992). "On minimal rectilinear Steiner
worstcase point set for the Euclidean Steiner problem is trees in all dimensions," to appear in Discrete &
asymptotically equidistributed. It is also likely that the Comp. Geom.; also in Proceedings of the Sixth
Steiner points in the Euclidean case are asymptotically Annual Symposium on Computational Geome
equidistributed. try (1990), Association for Computing Machin
A final open problem concerns the greedy matching. ery.
Though Condition 1 in Section 4 holds for this problem,
the methods used here to verify Condition 2 fail since a Steele, J.M. and Snyder, T.L. (1989). "Worstcase
g . reedy matching is not a matching of minimum length. growth rates of some classical problems of corn