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

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~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 <

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 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

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, 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.

.EW

M2 rn21 (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 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.

m

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

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 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

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 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