×

Cube versus torus models and the Euclidean minimum spanning tree constant. (English) Zbl 0781.60016

Summary: We show that the length of the minimum spanning tree through points drawn uniformly from the \(d\)-dimensional torus is almost surely asymptotically equivalent to the length of the minimum spanning tree through points drawn uniformly from the \(d\)-cube. This result implies that the analytical expression recently obtained by F. Avram and D. Bertsimas [ibid. 2, No. 1, 113-130 (1992; Zbl 0755.60011)] for the minimum spanning tree (MST) constant in the \(d\)-torus model is in fact valid for the traditional \(d\)-cube model. We also show that the number of vertices of degree \(k\) for the MST in both models is asymptotically equivalent with probability 1. Finally we show how our results can be extended to other combinatorial problems such as the traveling salesman problem.

MSC:

60D05 Geometric probability and stochastic geometry

Citations:

Zbl 0755.60011
Full Text: DOI