Cost of Sequential Connection for Points in Space.

摘要

A bound is given for the cost of the spanning tree produced by the sequential minimal insertion procedure as applied to n points in the unit d-cube. The technique developed is reasonably general and can be applied to several other problems of computational geometry, including the nearest neighbor heuristic for the traveling salesman problem. Attention is also given to bounding the sum of the powers of the edge lengths of sequentially constructed trees and paths. Examples illustrate that the bounds obtained are of best possible order as a function of the number of points. Keywords: Reprints. (kr)