| Let {lcub}X1,..., Xn{rcub} be i.i.d. random variables having values in [0, 1] d, d ≥ 2. Beardwood, Halton, and Hammersley (1959) show that the total edge length of the shortest tour through {lcub} X1,..., Xn{rcub} is asymptotic to a constant multiple of nd-1d with probability one. The asymptotic behavior of the total edge length of many classical graphs from combinatorial optimization is well known. This dissertation adds to this work by describing the stochastic behavior of the total edge length with pth power weighted edges of the Degree-k Minimal Spanning Tree and k-Tour Traveling Salesperson graphs for random point sets in [0, 1]d, when d ≥ 2 and 0 < p < d. This provides additional applications of the theory of Redmond and Yukich (1994, 1996). We also describe the stochastic behavior of the total edge length of some classical proximity graphs from computational geometry. Specifically, we describe the asymptotic behavior of the total edge length of the Delaunay Tessellation, Gabriel, and Relative Neighbors graphs for random point sets in [0, 1]d , d ≥ 2, as well as the total surface area, of the Voronoi Tessellation of random point sets in [0, 1]3. This adds to the work of Miles (1970) and McGivney and Yukich (1999). |
