| Let {dollar}{lcub}Xsb1,...,Xsb{lcub}n{rcub}{rcub}{dollar} be i.i.d. random variables on (0,1) {dollar}sp{lcub}d{rcub},d ge 2.{dollar} A classic result of Beardwood, Halton, and Hammersley (1959) states that as {dollar}n to infty{dollar} the length of the shortest tour through {dollar}{lcub}Xsb1,...,Xsb{lcub}n{rcub}{rcub}{dollar} is asymptotic to a constant multiple of {dollar}nsp{lcub}(d-1)/d{rcub}{dollar} with probability one. The stochastic behavior of a wide variety of problems in combinatorial optimization, computational geometry and operations research is well known. This thesis adds to this area by providing asymptotics for the k-median and k-nearest neighbors graphs as well as the Voronoi diagram. This extends upon the work of Hochbaum and Steele (1982) and Miles (1970). We also extend the work of Rhee (1993b) by proving a general umbrella theorem which is useful for obtaining asymptotics for functionals defined on random variables whose distribution has unbounded support. |
