Euclidean minimum spanning tree: Difference between revisions

Revision as of 04:46, 25 September 2022

Revision as of 07:28, 25 September 2022

Line 59:

===Two dimensions===

A faster approach to finding the minimum spanning tree of planar points uses the property that it is a subgraph of the Delaunay triangulation:

# Computation ofCompute the Delaunay triangulation, which can be done in <math>O(n\log n)</math> time. Because the Delaunay triangulation is a [[planar graph]], it has at most <math>3n-6</math> edges.

# Labeling ofLabel each edge with its (squared) length.

# RunningRun 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 result is an algorithm taking <math>O(n\log n)</math> time,{{r|shahoe}} optimal in certain models of computation (see [[#Lower bound|below]]).