Content deleted Content added
→Two dimensions: forward pointer to optimality |
→Two dimensions: fix |
||
Line 61:
# Label each edge with its (squared) length.
# Run a graph minimum spanning tree algorithm. Since there are <math>O(n)</math> edges, this requires <math>O(n\log n)</math> time using any of the standard minimum spanning tree algorithms.
The final result is an algorithm taking <math>O(n\log n)</math> time,{{r|shahoe}} optimal in certain models of computation (see [[#Lower
If the input coordinates are integers and can be used as [[array index|array indices]], faster algorithms are possible: the Delaunay triangulation can be constructed by a [[randomized algorithm]] in <math>O(n\log\log n)</math> expected time.{{r|bm09}} Additionally, since the Delaunay triangulation is a [[planar graph]], its minimum spanning tree can be found in [[linear time]] by a variant of Borůvka's algorithm that removes all but the cheapest edge between each pair of components after each stage of the algorithm.{{r|eppstein|mares}} Therefore, the total expected time for this algorithm is <math>O(n\log\log n)</math>.{{r|bm09}} In the other direction, the Delaunay triangulation can be constructed from the minimum spanning tree in the near-linear time bound <math>O(n\log^* n)</math>, where <math>\log^*</math> denotes the [[iterated logarithm]].{{r|devillers}}
| |||