Content deleted Content added
→Supergraphs: ce |
→Lower bound: say explicitly that the algorithms are optimal |
||
Line 84:
===Lower bound===
An asymptotic lower bound of <math>\Omega(n\log n)</math> of the Euclidean minimum spanning tree problem can be established in restricted models of computation. These include the [[algebraic decision tree]] and [[algebraic computation tree]] models, in which the algorithm has access to the input points only through certain restricted primitives that perform simple algebraic computations on their coordinates. In these models, the [[closest pair of points problem]] requires <math>\Omega(n\log n)</math> time, but the closest pair is necessarily an edge of the minimum spanning tree, so the minimum spanning tree also requires this much time. Therefore, algorithms for constructing the planar minimum spanning tree in time <math>O(n\log n)</math> within this model, for instance by using the Delaunay triangulation, are optimal.{{r|yao89}} However, these lower bounds do not apply to models of computation with integer point coordinates, in which [[bitwise operation]]s and [[Random access|table indexing]] operations are permitted using those coordinates. In these models, faster algorithms are possible, as described above.{{r|bm09}}
== Applications ==
| |||