On the asymptotic growth rate of some spanning trees embedded in ℝᵈ

We show that, for an Euclidean minimal k-insertion tree (EMIT_k) with n vertices, if the weight w of an edge e is its Euclidean length to the power of α, the sum of all w(e), with e ∈ EMIT_k, is O(n · k^−α/d) in the worst case, where d is the dimension, for d ≥ 2 and 0 < α < d. We also analyze the expected size of EMIT_k and some stars, when the points are evenly distributed inside the unit ball, for any α > 0. The paper has been published in Operations Research Letters, and can be found here.