Question

Suppose I randomly generate $n$ points from the unit square $[0,1]^2$, form a complete graph in which the weight of each edge is just the Euclidean distance between its endpoints, and compute the minimum spanning tree. I noticed empirically that the expected weight scales like $\sqrt{n}$. Using only back of the envelope arguments, how could I derive the $\sqrt{n}$ asymptotic behavior?

When I repeated the experiment in the unit cube $[0,1]^3$, the expected weight scaled like $n^{2/3}$, and when I repeated it on the unit hypercube $[0,1]^4$, the expected weight scaled like $n^{3/4}$. How could I derive this asymptotic behavior?

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top