Lower Bound
An asymptotic lower bound of Ω(n log n) for time complexity of the EMST problem can be established in restricted models of computation, such as 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 Ω(n log n) time, but the closest pair is necessarily an edge of the EMST, so the EMST also requires this much time. However, if the input points have integer coordinates and bitwise operations and table indexing operations are permitted using those coordinates, then faster algorithms are possible.
Read more about this topic: Euclidean Minimum Spanning Tree
Famous quotes containing the word bound:
“...the soul of Jonathan was bound to the soul of David, and Jonathan loved him as his own soul.”
—Bible: Hebrew (RSV)
“When I received this [coronation] ring I solemnly bound myself in marriage to the realm; and it will be quite sufficient for the memorial of my name and for my glory, if, when I die, an inscription be engraved on a marble tomb, saying, “Here lieth Elizabeth, which reigned a virgin, and died a virgin.””
—Elizabeth I (1533–1603)