1 Answers
A Euclidean minimum spanning tree of a finite set of points in the Euclidean plane or higher-dimensional Euclidean space connects the points by a system of line segments with the points as endpoints, minimizing the total length of the selected segments. In it, any two points can reach each other along a path through the line segments. It can be found as the minimum spanning tree of a complete graph with the points as vertices and the Euclidean distances between points as edge weights.
The edges of the minimum spanning tree meet at angles of at least 60°, at most six to a vertex. In higher dimensions, the number of edges per vertex is controlled by the kissing number of tangent unit spheres. The total length of the edges, for points in a unit square, is at most proportional to the square root of the number of points. Each edge lies in an empty region of the plane, and these regions can be used to prove that the Euclidean minimum spanning tree a subgraph of other geometric graphs including the relative neighborhood graph and Delaunay triangulation. By constructing the Delaunay triangulation and then applying a graph minimum spanning tree algorithm, a Euclidean minimum spanning tree for n {\displaystyle n} given planar points may be found in time O {\displaystyle O} , as expressed in Big O notation. Faster randomized algorithms are known for points with integer coordinates. For points in higher dimensions, finding an optimal algorithm remains an open problem.