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:
“I ask you to join in a re-United States. We need to empower our people so they can take more responsibility for their own lives in a world that is ever smaller, where everyone counts.... We need a new spirit of community, a sense that we are all in this together, or the American Dream will continue to wither. Our destiny is bound up with the destiny of every other American.”
—Bill Clinton (b. 1946)
“I’the commonwealth I would by contraries
Execute all things; for no kind of traffic
Would I admit; no name of magistrate;
Letters should not be known; riches, poverty,
And use of service, none; contract, succession,
Bourn, bound of land, tilth, vineyard, none;
No use of metal, corn, or wine, or oil;
No occupation; all men idle, all,
And women too, but innocent and pure.”
—William Shakespeare (1564–1616)