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:
“We that are bound by vows and by promotion,
With pomp of holy sacrifice and rites,
To teach belief in good and still devotion,
To preach of heaven’s wonders and delights—
Yet, when each of us in his own heart looks,
He finds the God there far unlike his books.”
—Fulke Greville (1554–1628)
“The essence of the modern state is that the universal be bound up with the complete freedom of its particular members and with private well-being, that thus the interests of family and civil society must concentrate themselves on the state.... It is only when both these moments subsist in their strength that the state can be regarded as articulated and genuinely organized.”
—Georg Wilhelm Friedrich Hegel (1770–1831)