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:
“... so far from thinking that a slaveholder is bound by the immoral and unconstitutional laws of the Southern States, we hold that he is solemnly bound as a man, as an American, to break them, and that immediately and openly ...”
—Angelina Grimké (1805–1879)
“Perhaps there are only a few women who experience without deception the overwhelming intoxication of the senses which they expect from their encounters with men, which they feel bound to expect because of the fuss made about it in novels, written by men.”
—Max Frisch (1911–1991)