Say we specify a number (n) of random points (x,y), bound within the axes and x=a, y=a.
Given the number of points and the constraints on the boundaries, how can you calculate the expected value of the weight or length of the minimum spanning tree defined by those points?
I've experimentally found the formula E = .6883*a*sqrt(x-2) to fit very well, but how can this be determined mathematically?
This is some data I got from running some tests. Contrained to a box with edge length 10, the blue dots represent the average weight of all MSTs in this box with number of points from 2 to 373. For each n, I randomly generated 100 sets of n points and then calculated the MST of each and took the average. The red dots show the graph of the formula I found experimentally.
Again, I'm wondering how I'd arrive at the expected value mathematically. Thanks for any help.
Ok, so this might be wrong, but here is a fuzzy argument for the growth rate of the function.
So lets assume that the square is of size $a$. The minimum spanning tree on $n$ points must be less than the sum of four minimum spanning trees on the square divided into 4 equal parts, each one connected.
So here is the fuzzy part, if we assume that the points are uniformly distributed, then might be able to assume that there are $n/4$ points in each of the four quadrants. Additionally, the pairwise distances of the points are scaled by half since we are halfing the $x$ and $y$ axis. So one gets the following recursion:
$$M(n) \leq \dfrac{4}{2}M(\frac{n}{4}) + O(a)$$,
Where $M(n)$ is the expected value of the MST of $n$ points. The recursion yields an $O(a\sqrt{n})$ solution. Of course, the expected value thing needs to be formalized but I think that is the general idea.
This is an upper bound, which seems to match your experimental results, so a lower bound might be possible. If you are careful, you might even find the constants! Although I think a lower bound will be hard, since adding an extra point to the rectangle can drastically change the MST.
Good luck!