A lower bound on . Let X(n) {x1, x2, . . . , xn} be a set of points uniformly and independently distributed in

A lower bound on β. Let X(n)  {x1, x2, . . . , xn} be a set of points uniformly and independently distributed in the unit square. Let (j be the distance from xj ∈ X(n) to the nearest point in X(n) \ xj . Let L(X(n)) be the length of the optimal traveling salesman tour through X(n). Clearly E(L(X(n))) ≥ nE((1).We evaluate a lower bound on β in the following way.

(a) Find Pr((1 ≥ ().

(b) Use

(a) to calculate a lower bound on E((1) 
 ∞
0 Pr((1 ≥ ()d(.

(c) Use Stirling’s formula to approximate the bound when n is large.

(d) Show that 1 2 is a lower bound on β.