JOURNAL OF COMPLEXITY 10, 230245 (1994)

General Spacefilling Curve Heuristics and Limit Theory

for the Traveling Salesman Problem

JUN GAO

Program in Statistics and Operations Research, School of Engineering, Princeton

University, Princeton, New Jersey 94305

AND.

J. MICHAEL STEELE*

Department of Statistics, Wharton School, University of Pennsylvania, Philadelphia,

Pennsylvania 19104

Received October 12, 1992

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 Vn times a periodic function of log n for a broad class of spacefilling curves. The theory is developed further by detailing the selfsimilarity 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. C 1992 Academic Press, Inc.

1. INTRODUCTION TO THE SPACEFILLING CURVE HEURISTIC

The basic ingredient of the spacefilling curve heuristic is a sudective mapping 0: [0, 11 [0, If such that for each x EE [0, 112 one can quickly compute a t EE [0, 11 such that 0(t) = x. The set of such ip is large, and any of these ip can be used to build heuristic methods for many problems of

Research supported in part by NSF. Grant D1IS9211634, and ARO Grant DAAL0391

G0110. Email steele@wharton.upenn.eud.

230 0885064X/94 $6.00 Copyright 0 1992 by Academic Press, Inc. AN rights of reproduction in any form reserved.

SPACEFILLING CURVES AND THE TSP 231

geometric combinatorial optimization. The main purpose of this article is to explore how these heuristics behave. For specificity we focus on the traveling salesman problem (TSP), and mainly we consider geometric features of the tours that one obtains on applying the heuristic to a random samples of points from [0, 111. Still, there is a general theme that is illustrated by these investigations, and it lives in the assertion that many methods of continuous analysis can be of use in problems of discrete optimization. This theme goes at least a little way to suggest that the classical theory of combinatorial computational complexity may not be as distant from the theory of numerical computational complexity as is commonly supposed.

The essential idea of the spacefilling curve heuristic applied to the TSP is the suggestion that we can find a short tour through a set of n points {xl, X2, . . . , Xn} C 10, 112 by visiting the points in the order of their preimages in [0, 1]. More formally, we have a threestep process where we (1) compute a set of points {tl, t2, . . . , Q C [0, 11 such that 0(t) = xi for each 1 :5 i n, (2) order the ti so that t(l) :5 t(2) :5 . . . :5 t(,), and, finally, (3) define a permutation or: [1, n] > [1, nj by requiring x,(i) qf(t(i)). The path that Visits {X 1 , X2, . . . ~ Xn} in the order of x,(,), X,(2), . , X,(n) Will be called the spacefilling curve path, and the tour that closes this path by adding the step from Xo.(n) back to x,.(,) will be called the spacefilling curve tour.

For the TSP heuristic built on a spacefilling curve 0 to be effective, one wants tP to be as smooth as possible. Many of the classical spacefilling curves are Lipschitz of order onehalf, which is to say there exists a constant cp so that for any 0 s, t 1 one has 110(s) 0(01 5 cpl S t1112. Furthermore, one can easily check that no spacefilling curve can be Lipschitz of order greater than onehalf. To see this, just note that the union of the images of [ilk, (i + 1)1k] for 0:s i < k must cover [0, 112, so at least one of these images must have diameter at least 27r112k111.

Many of the classic spacefilling curves have a further property that makes them particularly compatible with probabilistic investigations; they are measure preserving in the sense that for any Borel set A C [0, 112, X1W'(M) = XAM where Xd denotes the Lebesgue measure on Rd. In a later section, we will illustrate how this property helps one to translate many questions about random samples in [0, 112 to simpler questions about a random sample in [0, 11. This stochastic dimension reduction comes unbidden here, but in other contexts it can make light work of problems that otherwise would be perplexing.

As noted in the discussion by Adler (1986), the spacefilling curve heuristic for the TSP dates back at least to unpublished work of S. Kakutani in 1966. Still, the idea has become much better known and better understood since the work of Bartholdi and Platzman (1982, 1988). A particular distinction of these works is that they show that the required preimage

232 GAO AND STEELE

calculation can be done effectively and quickly. The works also illustrate that problems other than just the TSP can be addressed by use of the spacefilling curve heuristic, though on this point one should also note the independent developments of the spacefilling curve heuristic in communication theory by Bailey (1969), in matching theory by Imai (1986), and in real analysis by Kahane (1976) and Milne (1980).

Motivation for the present investigation comes in good part from a

probabilistic result of Platzman and Bartholdi (1989). Suppose Xi, 1 :~ i:~

n, are independent random variables that are uniformly distributed in [0,

I]', and let L SFC = LSFC(Xl, X2_

n . . , Xn) denote the length of a spacefilling heuristic path through {X,, X2, . . . , Xn}. Platzman and Bartholdi (1989) showed that for a specific 0, which had been designed to make the heuristic as effective as possible, there are two constants M' and )31 such that

SFC

lim sup ELSFW_n and lim sup EL n Wn,

n. n.

where j31 8 > 0.

Perhaps the most striking aspect of this result is that it offers a sharp

OPT(Xl, X2, Xn) of

contrast to the behavior of the length L nopT = L n

the shortest path through the random sample {X,, X2, XJ, for

which the famous theorem of Beardwood et al. (1959) tells us that there is

a constant 8 > 0 such that for n > we have

L 0.PTIVn_ , 0,

where the convergence takes place in expectation as well as with probability one.

One goal of this article is to develop the limit resultof Platzman and Bartholdi a bit further with the twin aims of laying out the explicit properties of 0 that are needed to provide an asymptotic understanding of the SF expectation of L n c and of rendering as precisely as possible the nature of

SFC

the oscillatory behavior of Ln Wn_. A second goal of this article is to

SK

complement the understanding of ELn with information on the behavior

SFC _ ELSFCJ _ t).

of the tail probabilities ^Ln n

Bartholdi and Platzman (1989) give few details in their discussion of the SFC almost sure behavior of L n , but part of the plan that they sketch offers to base the almost sure convergence theory of LnsFc on the methods of subadditive Euclidean functionals given in Steele (1981). Since there are substantial differences between the geometry of the spacefilling curve heuristic and that of subadditive Euclidean functionals, this approach does not seem to be an easy one. In contrast, there are major benefits to

SPACEFILLING CURVES AND THE TSP 233

SK be found in basing the almost sure analysis of Ln on martingale difference methods. By applying martingale methods developed for the analysis of optimal TSP tours, one needs little work to produce strong bounds

SK _ EL SK1

on the tail probabilities P(JL, n ~: t). In turn, these make quick

and complete work of the almost sure behavior of L nsFe while contributing

additional understanding of the whole process.

2. STRUCTURAL ASSUMPTIONS AND MAIN RESULTS

For all of the results considered here we assume our spacefilling curves are measure preserving and Lipschitz of order onehalf; but, to obtain a

SK serious asymptotic understanding ofEL,, one seems to need to bringout further properties of tp. The properties described below are found in many of the classical spacefilling curves, and they reflect the important fact that most of the classical spacefilling curves (such as those of Hilbert (1891) or Peano (1890)) have aspects of selfsimilarity.

AI. Dilation Property. There is an integer p 2 such that for all 0 :S

S, t 1,

110(s) 0(01 ~ltp 0 ( t)

p p

A2. Translation Property. For 1 ~5 i:s p, if (i 1)lp:s s, t:s ilp, then

110(s) 0(01 = 110(s + 1/P) mt + I/01.

A3. Bimeasure Preserving Property. Given any Borel set A in [0, 1], one has

XI(A) = A2WAD,

where Xd is the Lebesgue measure on Rd. The main results of this article are the following two theorems.

THEOREM 1. If a heuristic tour is built using a spacefilling curve 0 that satisfies the Dilation Property (AI), the Translation Property (A2), and the Bimeasure Preserving Property (A3), then there exists a continuous function ~p of period of 1 such that

lim _EL SEc

xln~o(logp n) where p is the integer appearing in assumptions AI and A2.

1

234 GAO AND STEELE

THEOREM 2. If a spacefilling curve ~p has the Bimeasure Preserving Property (A3), then there are constants A and B such that for all t ~~ 0,

SK ELSFC

P(IELn n 1 ~~ t) ~~ B exp(At2/10g t).

3. PROOF OF THEOREM 1

We first record a simple lemma that makes explicit the correspondence created by tp between uniform random variables in [0, 112 and [0, 11.

LEMMA 1. Suppose X is a random variable that is uniformly distributed in [0, 1]2. Let tp* be a function that for every x EE [0, 112 selects a preimage of x, that is, tp* satisfies tp(qj*(x)) = x. For t defined by t = 0*(X), we have that, if the spacefilling curve satisfies the bimeasure preserving assumption A3, then t is uniformly distributed in [0, 1].

The proof of the lemma can be safely omitted, but one should note that there are measure preserving mappings ip that satisfy AI and A2 while failing to have A3 and failing to have the correspondence property. By the lemma, an independent uniform random sample {X,, X2, . XJ C [0, 112 corresponds under 0* to a uniform random sample {tj, t2, SFC

tn} C [0, 11. Thus, the length L n of the path provided by spacefilling heuristic is given by

n~l

LSFC =

n 110(tw) 0(t(i+l))11,

where t(l),, t(2) :5 :5 t(n) are the order statistics of ti, t2, 4. On

taking the expectation we find

n1

ELSK fl f' 110(s) ip(t)iifi(s, t) ds dt,

n 00

where fi(s, t) is the joint density of Q(,), t(i+ 1) given by

Ms' t) = n! si10

(i 1)!(n i 7M

Here we should remark that this last density formula, as well as those we use subsequently, can be obtained in many ways, through the most general of these seems to be direct integration of the full joint density of (t(l):5 t(2):5 . . . :5 t(n)). If we write the basic simplex as Sn = {(Xl, X2, . . . ' XJ: 0 < xl < . . . < x,, < I}, then the fundamental fact is that (t(l) :5 t(2) 25

'IT

SPACEFILLING CURVES AND THE TSP

235

t(,)) has the density n! I&(x 1 , X2, . . . , x,,), and specialized distributional information about individual variables (or pairs of variables) thus can be obtained by direct integration. For illustrations of the use of the uniform distribution on the simplex to obtain the derivation of expressions like that given forfi(s, t), one can consult Devroye (1986).

The following elementary lemma points out a somewhat surprising formula for the sum of the joint densities of successive order statistics. We

SFC

will use it to write ELn in a simpler form.

LEMMA 2. For 0 :~ s < t 5 1, we have

n1

fi(s, t) = n(n t + S)n2.

Proof.

n~l n12

f

i(S, t) t)

P(t(i) S, t(i+j)

asat

a2 n1

= 1

asat i=, LI fos

a2 as

at i!(n i)!

= a2 11 (

asat

n!

(i 1)!(n i 1)!

n ! si[(1 S)ni (1 t)nil

ui1(1 V)n~i1 du dv

1 Sp (1 t + S)n + (1 t)nl

= n(n 1)(1 t + S)n2. a

SF

By substituting (1) into the integral representation for ELn c and letting

x = t s, we have

ELSK = 1X

n fol fo 110(s + x) qj(s)iln(n 1)(1 X)n2 ds dx.

This is a charming exact formula for the expected length of the heuristic tour, but there is an approximate formula that is a bit simpler and more natural for asymptotic analysis.

LEMMA 3.

EL!FC = n 3/2 fII fll~x

Vn_ 0 0

liqj(s + x) 0(s)iie ds dx + o(l).

236 GAO AND STEELE

Proof. We have to estimate the absolute value A, of the difference between the principal terms

' f' f,'x 110(s + x) tP(s)lin(n 1)(1 x)"'~ ds dx

Vn 0 0

and

n3/2 fo' fo' 110(s + X) owile ds dx.

From the completely crude bound 110(s + x) tp(s)~] :5 V2, we see

1

An :S V2 f. 1n112(n X)n2 n312enxidx,

and since 1(1 X)n2 enxl :5 f(l X)n (1 Xp2} + {enx (1 X)n} easy integrations Show An = 0(n112), leaving room to spare.

If we define the function k(x) by

k(x) = 1X tp(s)iids,

fo lio(s + X)

then by the usual considerations of Laplace's asymptotic method, the behavior of EL nsFc/ Vn is determined by the behavior of k(x) in the neighborhood of 0, so we may just as well write

EL Sn FC = n3/2 fq k(x)e dx + o(l),

Vn 0

where q = 11p.

We can now generalize an observation from Platzman and Bartholdi (1989) to show there is a function r(x) that captures the scaling properties of 0, and, at the same time, offers an approximation for the function k(x).

LEMMA 4. For q = 1 lp, one can define a continuous function r on [0, with the following properties: (a) r(x) :5 cpVx, 0 :5 x < . (b) ik(x) r(x)i 5 cqx111, 0 :S x q. (c) r(x) = Vpr(xlp), 0 x < ..

Proof. For any 0 :5 x :5 q, we see from the definition of k(x) that

p iq1

k(x) litp(s) tp(s + x)iids. (1)

SPACEFILLING CURVES AND THE TSP 237

Next, by assumption A2, changing variables, and using assumption AI, we obtain

P qx

x 110(s) 0(s + x)ilds = p liqj(s) O(S + x)ilds

_,)q f,

= fpqpv (s + Px ~l ds

0 p p )

1 = fo,px 110(s) p(s + px)llds

7P

1 k(px). (2)

VP_

By combining (1) and (2), we find the basic fact

k(x) ~: 1 k(px). (3)

VP_

If we replace x by xlp, in inequality (3), we then have k(x) 2s Vp_k(xlp) for 0 :5 x :s 1. Thus, if we define a sequence of functions {f,,(x)},~to by

f ~_ pn1,

.(X) = pn12k P. 0 < X

(i),

then these functions are pointwise monotonic on ever increasing intervals:

AW :5A+1(x) 0:5 X:5 p (4)

By the Lipschitz property of 0, we have k(u) :5 cp u for 0 :5 u :s 1, so for 0 5 x 5 pnl we have

f

.(X) :5 p(nll)IC,,VXlpol = C'PVX. (5)

The last two inequalities show that for all x 2t 0 that {f,(x)} is a bounded, monotone sequence. We will denote the limit by r(x) and show that this r(x) satisfies the requirements of the lemma. To begin, we see that letting n co in (5) already yields requirement (a).

To obtain the other required properties of r(x), we introduce a sequence of functions g,, that we can show will decrease to r(x). We let

go(X) = C'PX312 + k(x),

238 GAO AND STEELE

and we note by (2) that for 0 :jE~ x :~ q we have

{ P iqx ' iq

go(x) 1 f 110(s) MS + x)llds + P 110(s) qj(s + x)l~ds

i=l U1)q 71 fi

+ COX3/2

P' iq

k(px) + f 110(s) 4j(s + x)llds

iqx

+ {CPpX111 Co(p 1)X312}

k(px) + CopX112 + P' iq

1 Rqx 110(s) 0(s + x)llds COXII2

VP_

(6)

By the Lipschitz property of ip, we have

fiq li~(S) O(S + X)11dS COX312 ~_ 0,

iqx

so after replacing x by xlp, we have for 0 x 1 that go(x) ~~: \1pgo(xlp). We rescale go to define g,(x) = pn12go(X1pn) and note that our inequality for go yields the monotonicity relation:

9,1W gnll(X), 0 25 X < pnl.

The definition of g, tells us

g f

n(X) ~(X) = CX3121pn, 0 < X :5 pn1, (7)

SO gn(x) also converges to r(x) as n This implies that for 0 :s x

pn1,

fn(x) :5 r(x) :5 gn(X). (8)

To show the part (b) we just need n = 0 to see that for 0 :5 x :5 q

k(x) = fo(x) :5 r(x) 5 go(x),

and, consequently,

f

lk(x) r(x)J:51go(x) O(X)I= COX312 0 x q.

SPACEFILLING CURVES AND THE TSP 239

All that is left to finish the proof is to establish (c), but this is almost immediate by the definition of r. We have r (:~) = lin, p,12k ( x

p pl. pn~l

= lim (n + 012k

n_. p

X/P_

r(x)

X/P_

completing the proof of the lemma.

To bring r(x) into action, we note that by the first two parts of the lemma, we have

ELSK n = n3/2 fq r(x)e dx + o(l),

Vn_ 0

= n312 f r(x)e dx + o(l). (9)

Still, the power of this representation is evident only when we use the third part of the lemma to connect r(x) to a periodic function of logp n.

LEMMA 5. There is a continuous function ~o: [0, [0, ) with

period 1 such that

cp(logp n) = nlll.f,' r(x)e dx.

0

Proof. We let I(n) denote the right hand side, divide the interval [0, into subintervals [pkIn, pk+11n], < k < oc, and the make the change of variables x = pk+uln on the subinterval [plIn, pk+11n] to get

An) = n312 pk+11n r(x)e dx

k= PkIn

= Vn j 1 r(pk+111n)pk+u eXp(_pk+u) In p du.

k= fo

By Lemma 4, part (c), we have

240 GAO AND STEELE

I(n) = n 1/2 r(plIn)p3k12+ii exp(pk+11 ) In p du

0

= In p r(P iilog,n p (312)(k+u) exp(p`11) du.

fo

We then define the function (p by

(p(x) = In p fo 1 r(p(~'u))1"Y~h(ti) du,

where h is defined by

h(u) p 312(k+ii) exp(pk+u) du.

k=

We note that both h and ~p are continuous, and by the integral representation for I(n) we have

I(n) = ~o(logp n).

Next, to check that ~p is periodic function with period 1, we just note that r(x) = Vp_r(xlp) tells us

~p (x + 1) = In p fo 1 r(p(X+IU))IV7 (u) du

= In p f,' Vpr(p(xu)lp)IV''~h(u) du

(p (X) (10)

Finally, we check that (p is bounded from below by a positive constant. To begin we note that by continuity and periodicity there would otherwise be an xo such that ~o(xo) = 0. But by the integral definition of (p this would imply that r vanishes on the interval [pxo, pxo+11, and this in turn would imply that r is identically zero by the recursive property of r in Lemma 4. Hence we conclude that p never vanishes and consequently is bounded below by a positive constant.

Dividing both sides of (9) by ~o(log, n) and applying Lemma 5, we have proved that

EL WC

lim n_ _ = 1.

Vn~o(logp n)

SPACEFILLING CURVES AND THE TSP 241

4. PROOF OF THEOREM 2

To set up the application of martingale differences, we first let Yk be the

oficld generated by {Xl, X~,, . . . , XJ, and then define

SKI 5;i)

di = E(Ln E(Ls,Fc~ji,). (11)

Once can easily check that {di, 1 :s i :5 n}, is a martingale difference sequence and that we have the basic representation

11

LSFC ELSK d.

This type of representation for the optimal tour length L, was introduced in Rhee and Talagrand (1987), and its application was subsequently refined in Rhee and Talagrand (1989b). One can consult these articles for additional information on the role of martingales in problems such as the TSP; and, for general background on the applications of martingales in combinatorics, one does very well by consulting Chap. 7 of Alon et al. (1992).

For the path taken here, we recall two results from Steele (1989). The first is a rather special LP inequality that requires some machinery from martingale theory for its proof, but the second is just an exercise in applying Markov's inequality.

LEMMA 6. Let di, 1 :5 i:5 n, be a martingale difference sequence. If there are two constants cl and C2 such thatfor p > 1 and 1 :5 i :5 n we have

Ildill. :5 cl(n i + 1)1/2, and

Ildill, :5 CApIn)111 then there is a constant C3 such that

n

:5 C,p112(log p) 112.

LEMMA 7. For any random variable Z, there are constants a and b so that

^IZI ~: t) :s a exp(bt2/log t), t 0,

242 GAO AND STEELE

if and only if, there is a constant c such that for all p ~: 1 that p :E~ CP 1/2(1 og p) 1/2.

The proof of Theorem 2 thus reduces to showing that the martingale differences defined in (11) satisfy the conditions of Lemma 6. To reexpress those conditional expectations in a more convenient form, we introduce independent random variables {Xi: 1 :s i ::~ n} with the uniform distribution on [0, 112 that are also independent of {Xi: 1 :5 i ~5 n}, and we define L SFC(i) = LSFC (X,, X2, . .

n . , Xi1, ~Ci, Xi,1, Xj. The purpose of introducing these variables is that we find the new representation

SK SK(i)l 9~i).

di = E(Ln Ln

Now we need to find bounds on dj. In sympathy with our earlier notation, we put ii = 0 *(£i), and, for our first crude bound, we use the definition of the heuristic and the Lipschitz property of 0 to find

I SFC SK(i)l

Ln Ln :5 2co min 1 ii tj 1 112 + 2cp rnin 1 ti tj 1 1'2.

i

The reason for the restriction on the j's is brought out when we take expectations and use independence to get the bound

SK SFC(i)i S;i)l SK SF%)11 yi)

Idil = IE(Ln Ln :5 EflLn Ln

:5 2c0E(min Iii tj1112) + 2cpE(min Iti tj 1 1/21 9;i). (12)

i

To complete the computation of these expectations, we note the easy bounds on the tail probabilities

P(min iii tj1112 t) = P(min Iii tjl ~t t2) 5 (1 t2)ni,

i

and

P(min Iti tj11'2 tl 9;j) :5 (1 t2)ni.

i

Since there is a constant a, such that for all m,

f1 (1 t2) dt = 1 7r112F(m + I)/IF(m + 3/2) :5 al(m +

o 2

1

SPACEFILLING CURVES AND THE TSP 243

we see there is a constant a2 such that

E min tj £ P (min tj1112 t) dt ::i~ a2(n i + 1)1/2

i

and

E(min 1 ti tj 1 1/21 y,,) :5 a2(n +

i

By applying these two bounds in (12) we see that we have established the first condition of the lemma.

Now, we show that there is constant C2 such that

Ildill, CApIn) 1/2.

By the definition of di and Jensen's inequality, we have

SFC SF%) 1 9~i) 1 p SFC SK(i)l p.

Eldi1P = E1E(Ln Ln E1Ln Ln

For p 1 and x ~t 0, y ~~ 0 we have 1x + y JP 2P(xP + yP), so

Eldi1P 2PcpE(min Iti tj1p12) + 2PcOE(min Iti tj1P12).

i2~jsn joi

To bound the last two expectations, we note

1 p

E min Iii tj1P12 tpl2p(min Iii tjl ~~: t) dt

i~tj:sn i2~jsn

:5 P tp/210 W1 dt np12r(p/2)

2 fo 2

c(pIn)P1,

and by a completely parallel argument we also find

E (min 1 ti tj 1 P11) :5 c (p In) P/2;

j94i

so the second inequality in the hypothesis of Lemma 6 is proved. By applying Lemma 7, we conclude the proof of Theorem 2.

Application to Almost Sure Convergence

By Theorem 1 and Theorem 2 together with the traditional BorelCantelli argument, we find the desired strong law:

244 GAO AND STEELE

LsFC

lim 'I = 1 a. s.

X/"nsc(log, n)

One should note that Theorem 2 goes much further than is required for this law; and, in most cases, one does better to use Theorem 2 directly, rather than to call on this corollary. Still, because of the natural connection to the BeardwoodHaltonHammersley theorem and the results of Platzman and Bartholdi (1989), the application deserves to be singled out.

5. CONCLUSION

There are two open problems that seem particularly compelling.

1. Is there a spacefilling curve 0 for which the corresponding periodic function ~o is actually a constant? One may have to give up some of the efficacy of the heuristic tours provided by the 0, but one would regain the fundamental behavior of the optimal tours as reflected in the BeardwoodHaltonHammersley theorem. We know from direct computations done in Platzman and Bartholdi (1989) that there are 0 for which (p is nonconstant, but it would be surprising if there were no 0 for which T is constant. After all, as the works of Salem and Zygmund (1945) and many others show, there are methods for constructing bimeasure preserving, Lipschitz onehalf, spacefilling curves that apparently have little to do with the selfsimilarity properties AI and A2.

2. Can the tail bound of Theorem 2 be improved to provide a bound of the Gaussian form, where no log t factor is required? That is, can one show that for any Lipschitz onehalf, bimeasure preserving, spacefilling curve that one has constants A and B such that for all t =t 0 one has

PSFC ELSK1

(ILn n ~ t) :5 B exp(At2).

We know from the developments of Rhee and Talagrand (1987, 1989a, and particularly 1989b) that the corresponding Gaussian tail bound does hold for the length of the shortest path. Such an inequality for the spacefilling heuristic paths would seem to be easier than that for the optimal paths, but the problem still does not seem to be easy. Apparently, one cannot easily adapt the method of Rhee and Talagrand (1989b) to obtain a Gaussian tail bound for the length of the spacefilling curve heuristic paths.

REFERENCES

ADLER, R. (1986), Conimentary, inTheCollected Works of S. Kakutani, Vol. IF' (R. R.

Kalman, Ed.), p. 444, Birkhauser, Boston, 1986.

SPACEFILLING CURVES AND THE TSP 245

ALON, N_ SPENCER, J. H., AND ERD6S, P. (1992), "The Probabilistic Method, WileyInterscience Series in Discrete Mathematics and Optimization, New York.

BAILEY, T. (1969), Spacefilling curves: Their generation and their application to bandwidth reduction. IEEE Trans. Inform. Theory 11.15, 658~664.

BARTHOLDI, J. J., AND PLATZMAN, L. K. (1982), An 0(n log n) Planar traveling salesman heuristic based on spacefilling heuristic curves, Oper. Res. Lett., 121125.

BARTHOLDI, J. L, AND PLATZMAN, L. K. (1988), Heuristics based on spacefilling curves for combinatorial problems in Euclidean space, Management Sci. 34(3), 291305.

BEARDWOOD, L, HALTON, J. H_ AND HAMMERSLEY, J. M. (1959), The shortest path through many points, Proc. Cambridge Philos. Soc. 55, 299327.

DEVROYE, L. (1986),NonUniform Random Variate Generation, pp. 1719, SpringerVerlag, New York.

HILBERT, D. (1891), Ober die Stetige Abbildung einer Linie auf ein F19chenstack, Math. Ann. 38, 459460.

IMAI, H. (1986), Worst case analysis for planar matching and tour heuristics with bucketing techniques and spacefilling curves, J. Oper. Res. Soc. Japan 29(1), 4367.

KAHANE, LP. (1976), Mesure et dimensions, in Turbulence and Navier Stokes Equations" (A. Dold and B. Eckmann, Eds.), Lecture Notes in Mathematics, Vol. 565, SpringerVerlag, New York.

MILNE, S. C. (1980), Peano curves and smoothness of functions, Adv. Math. 35, 129157.

PEANO, G. (1890) Sur une courrbe qui remplit toute une aire plane, Math. Ann. 36, 157160.

PLATZMAN, L. K., AND BARTHOLDI, J. J. (1989), Spacefilling curves and the planar traveling salesman problem, J. Assoc. Comput. Mach. 36(4), 719737.

RHEE, R. T., AND TALAGRAND, M. (1987), Martingale inequalities and NPcomplete problems, Math. Oper. Res. 12, 177181.

RHEE, R. T., AND TALAGRAND, M. (1989a), Martingale inequalities, interpolation and NPcomplete problems, Math. Oper. Res. 14, 9196.

RHEE, R. T., AND TALAGRAND, M. (1989b), A sharp deviation for the stochastic traveling salesman problem, Ann. Probab. 17, 18.

SALEM, R., AND ZYGMUND, A. (1945), Lacunary power series and Peano curves, Duke Math. J. 12, 569578.

STEELE, J. M. (1981), Subadditive Euclidean functionals and nonlinear growth in geometric probability, Ann. Probab. 9, 365376.

STEELE, J. M. (1989), Seedlings in the theory of shortest paths, in Disorder in Physical Systems: A Volume in Honor of J. M. Harnmersley" (G. Grimmett and D. Welsh, Eds.), Cambridge Univ. Press, Cambridge, MA. ,