Minimum-diameter spanning tree

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.

In general metric spaces

It is always possible to find a minimum-diameter spanning tree with one or two vertices that are not leaves. In the case of two non-leaf vertices, every leaf can be connected to its nearest neighbor among the two non-leaf vertices. This can be proven by transforming any other tree into a tree of this special form, without increasing its diameter. To do so, consider the longest path in any given tree (its diameter path), and the vertex or edge at the midpoint of this path. If there is a vertex at the midpoint, it is the non-leaf vertex of a star, whose diameter is at most that of the given tree. If the midpoint is interior to an edge of the given tree, then there exists a tree that includes this edge, and in which every remaining vertex is a leaf connected to the nearest endpoint of this edge, with diameter at most that of the given tree.

Because of this special form, it is possible to construct a minimum-diameter spanning tree of $n$ points in time $O(n^{3})$, assuming that the distance between two points can be computed in constant time. To do so, find a set of candidate trees, including a star for each given point, having that point as its non-leaf vertex, and a tree for each pair of given points, connecting all remaining points to the nearest point in the pair. There are $O(n^{2})$ candidate trees, each of which can be evaluated in time $O(n)$, giving a total time bound of $O(n^{3})$.

The problem of constructing a minimum-diameter spanning tree is different from computing the diameter of the given points, the maximum pairwise distance. For some sets of points, the diameter of the points and the diameter of their minimum-diameter spanning tree are equal; for others (for instance, three equidistant points) these two distances can differ from each other by a factor of two.

In graphs

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. However, this may require it to have more than two non-leaf vertices. 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. Among such points, the absolute 1-center is a point minimizing the maximum distance to all vertices. The shortest-path tree from this point to all vertices in the graph is a minimum-diameter spanning tree of the graph. The absolute 1-center problem was introduced long before the first study of the minimum-diameter spanning tree problem, and in a graph with $n$ vertices and $m$ edges it can be solved in time $O(mn+n^{2}\log n)$.

In the Euclidean plane

The exact solution of the minimum-diameter spanning tree problem, in the Euclidean plane, can be sped up from $O(n^{3})$ to $n^{17/6+o(1)}$, 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. In $d$ dimensions, the time bound for this method is

$\displaystyle O\left(n^{3-{\tfrac {1}{(d+1)(\lceil d/2\rceil +1)}}+o(1)}\right).$

A polynomial-time approximation scheme is known for the minimum-diameter spanning tree in the plane. For any $\varepsilon >0$, one can find a tree whose diameter is at most $1+\varepsilon$ times the optimum, in time $O(n+\varepsilon ^{-3})$. 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.

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. This approximation can be found in time $O(n^{2}\log n)$, and achieves an approximation ratio of ${\tfrac {4}{3}}$.

With only one non-leaf

For the minimum-diameter tree among trees with only one non-leaf vertex, the non-leaf vertex of the tree is the 1-center of the points.

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. Its diameter is twice the radius of this sphere. 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.