Asymptotic worst case lengths in some problems from classical computational geometry and combinatorial optimization
Timothy Law Snyder · 1987
A method is presented for determining the exact asymptotic worst case behaviors of some quantities from classical computational geometry and combinatorial optimization. We begin with the length of a worst case minimal spanning tree and the length of a worst case optimal traveling salesman tour of n points in the unit d-cube, where d = 2. For each of these problems, we prove that the worst case lengths have exact asymptotic growth rates of (beta)n('(d-1)/d) as n (--->) (INFIN). We next consider the length of worst case greedy and minimal matchings, where the edge-weighting function is taken to be the (alpha)'th power of Euclidean distance, and where 0 < (alpha) < d. These quantities are each proved to have an exact asymptotic growth rate of (beta)n('(d-(alpha))/d). We also prove additional theorems for the greedy matching, including a minimax theorem that addresses the existence of different greedy matchings resulting from ties in edge lengths in the complete graph on a given set of points. It is shown that the worst case performances of an optimal greedy algorithm and a greedy algorithm that produces the worst possible greedy matching of a given point set are identical for all n (GREATERTHEQ) 1. In addition, we prove several other combinatorial and geometric results for all four of our problems. Although our method is robust enough to capture the worst case asymptotic lengths for all these problems, each new problem possesses special characteristics that require us to obtain some new geometric information before our method can be applied. We explicate some general tools of the method that are sufficient to yield results analogous to ours for classical problems of a similar nature. The above results complement known results for analogous growth rates under probabilistic settings, but in our worst case analyses we assume no probabilistic hypotheses. We discuss in detail the implications of these results.