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 worst case point set A worst case 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 worst case TSP tour and its associated point
imation algorithm for the worst case Euelidean TSP.
Analogous results are proved for the rniinimum spanning set a worst case TSP point set.
tree, minimurn weight matching, and rectilinear Steiner The first works on the sequence PTSP(n) were
minimum tree. These equidistribution theorems are the the lower bounds of Fejes T6th (1940) and the up
first results concerning the structure of worst case point per bounds of Verblunsky (1951). Successive improve
sets like S(n). ments to these bounds and their higher dimensional
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 worst case 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 worst case 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 worst case
total length minrf jel : T is a tour of S }. Here, tour. Let S(n) be a worst case 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 DMS92 11634, NSA MDA904 89 H 2034, AFOSR 89 0301, and ARO DAAL03 91 G 0110.
1 1
EQUIDISTRIBUTION OF POINT SETS FOR THE TRAVELING SALESMAN 463
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~t case lim (2.1)
TSP point sets is asymptotically equidistributed: n oo 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 worst case T5P point sets, then, for any rectangle number of points in the ith cell of a worst cue 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 worst case 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 worst case 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 <
ITSP(S(n))J.
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 equally sized 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
464 SNYDER AND STEELE
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, within cell 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 within cell 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.
.EW
M2 rn2 1 (2.5) ProoŁ
ITSP(S(n) n Qi) 1 + 2 lei 1
First note that V,, can be written as
rn2
< 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,
i=l
PTSP(n) =fln1/2 + r(n) applying Lemma 1 to the second term of (2.9) gives
M2
< 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).
M2
+ 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
'n~
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
EQUIDISTRIBUTION OF POINT SETS FOR THE TRAVELING SALESMAN 465
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
(n)
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
S(n
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 worst case (within cell) lengths
;~ 2 DS( M 1PMST(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.
m
Theorem 2. If { S,(n) : 1 < n < w } is a sequence
Squaring (3.2) yields Theorem 1. of worst case 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 minimum length The asymptotic equidistribution of worst case 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 worst case point sets are approxi
n
F,
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 worst case 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
466 SNYDER AND STEELE
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 worst case length of the TSP has been FeJes T6th, L.T. (1940). "tber ein geometrische Satz,"
known for several years, an equidistribution result for Math. Zeit. 46, 299 327.
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 worst case road through n points in a region," Mathe
point sets, however, this result is only of theoretical in matika 2, 141 144.
terest; whether it can be used for point sets other than Goddyn, L. (1990). "Quantizers and the worst case 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 rninimum length 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, 91 99.
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 worst case 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, 1 19.
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, 113 141,
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
worst case 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). "Worst case
g . reedy matching is not a matching of minimum length. growth rates of some classical problems of corn