Several algorithms have been developed for general graphs with arbitrary
Chazelle presented an
O(mα(m, n)logα(m, n))-time algorithm
and then an
O(mα(m, n))-time algorithm [Cha00b],
α(m, n) is the functional inverse of Ackermann's function,
and n and m are the number of vertices and edges respectively
in the graph.
Pettie and Ramachandran have since given an optimal algorithm for the graph
setting [PR02], whose running time is an unknown function between
In particular, when
m = Ω(n log n),
α(m, n) = O(1) and
these time bounds are all linear in the number of edges, m.
But in the geometric setting, the graph is complete, so a time bound linear
in the number of edges, m, is quadratic in the number of points, n.
And indeed the best upper bounds for the Euclidean
MST approach quadratic for large d, e.g., [CK95].