In metric geometry and computational geometry, a minimum-diameter spanning tree of a finite set of points in a metric space is a spanning tree in which the diameter (the longest path length in the tree between two of its points) is as small as possible.
[1] It is always possible to find a minimum-diameter spanning tree with one or two vertices that are not leaves.
[1] Because of this special form, it is possible to construct a minimum-diameter spanning tree of
, assuming that the distance between two points can be computed in constant time.
candidate pairs of non-leaf points, each of which can be evaluated in time
, giving a total time bound of
[1] The problem of constructing a minimum-diameter spanning tree is different from computing the diameter of the given points, the maximum pairwise distance.
For the metric space of shortest-path distances in a graph, a minimum-diameter spanning tree can also be a spanning tree of the graph, a tree whose edges all belong to the graph.
In this case, the problem is equivalent to finding an absolute 1-center of the graph.
This is a point in a metric space obtained from the given graph by replacing each edge by a continuous interval of the same length.
That is, it can either be a vertex or it can lie partway along any edge of the given graph.
[2] The absolute 1-center problem was introduced long before the first study of the minimum-diameter spanning tree problem,[2][3] and in a graph with
[2][4] The exact solution of the minimum-diameter spanning tree problem, in the Euclidean plane, can be sped up from
, at the expense of using complicated range search data structures.
The same method extends to higher dimensions, with smaller reductions in the exponent compared to the cubic algorithm.
dimensions, the time bound for this method is A polynomial-time approximation scheme is known for the minimum-diameter spanning tree in the plane.
The algorithm involves approximating the input by the points of a coarse grid, chosen to give the best tree among a small number of grid orientations.
[6] For points in the Euclidean plane, the minimum-diameter spanning tree problem can also be approximated by the minimum-sum dipolar spanning tree.
This is a tree having two non-leaf vertices, minimizing the sum of two quantities: the distance between the two non-leaf vertices, and the largest distance from a leaf vertex to the closer of the two non-leaf vertices.
If additional Steiner points are allowed to be added to the given set of points, their addition may reduce the diameter.
In this case, a minimum-diameter Steiner spanning tree exists with only one non-leaf vertex, a Steiner point at the center of the smallest bounding sphere of the points.
For points in a Euclidean space of bounded dimension, this sphere and this tree can be found in linear time using algorithms for the smallest-circle problem and its generalizations.