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.^[1]

It is always possible to find a minimum-diameter spanning tree with one or two vertices that are not leaves. 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 endpoint of this edge that is nearest in the given tree, with diameter at most that of the given tree.^[1]

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, test all candidates for the single point or pair of points that are not leaves. Each single point can be tested in $O(n)$ time. Each pair of points can also be tested in $O(n)$ , after a precomputation step in which, for each point, the other points are sorted by their distance from it. To test a pair of points, start with a tree in which all remaining points are attached to one point of the pair, and then in decreasing order by distance from that point, reattach these points one at a time to the other point of the pair, keeping track of the diameter of the tree at each step. There are $O(n^{2})$ candidate pairs of non-leaf points, each of which can be evaluated in time $O(n)$ , giving a total time bound of $O(n^{3})$ .^[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 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 on a weighted undirected 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.^[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 $n$ vertices and $m$ edges it can be solved in time $O(mn+n^{2}\log n)$ .^[2]^[4]

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).

^[5]

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

With only one non-leaf

References

1 2 3 4 Ho, Jan-Ming; Lee, D. T.; Chang, Chia-Hsiang; Wong, C. K. (1991), "Minimum diameter spanning trees and related problems", SIAM Journal on Computing, 20 (5): 987–997, doi:10.1137/0220060, MR 1115662
1 2 3 Hassin, Refael; Tamir, Arie (1995), "On the minimum diameter spanning tree problem" (PDF), Information Processing Letters, 53 (2): 109–111, doi:10.1016/0020-0190(94)00183-Y, MR 1314717
↑ Hakimi, S. L. (June 1964), "Optimum locations of switching centers and the absolute centers and medians of a graph", Operations Research, 12 (3): 450–459, doi:10.1287/opre.12.3.450, JSTOR 168125
↑ Kariv, O.; Hakimi, S. L. (1979), "An algorithmic approach to network location problems, I: The $p$ -centers", SIAM Journal on Applied Mathematics, 37 (3): 513–538, Bibcode:1979SJAM...37..513K, doi:10.1137/0137040, MR 0549138
↑ Chan, Timothy M. (2003), "Semi-online maintenance of geometric optima and measures", SIAM Journal on Computing, 32 (3): 700–716, doi:10.1137/S0097539702404389, MR 2001751
↑ Spriggs, Michael J.; Keil, J. Mark; Bespamyatnikh, Sergei; Segal, Michael; Snoeyink, Jack (2004), "Computing a $(1+\epsilon )$ -approximate geometric minimum-diameter spanning tree", Algorithmica, 38 (4): 577–589, doi:10.1007/s00453-003-1056-z, MR 2032526
↑ Gudmundsson, Joachim; Haverkort, Herman; Park, Sang-Min; Shin, Chan-Su; Wolff, Alexander (2004), "Facility location and the geometric minimum-diameter spanning tree", Computational Geometry, 27 (1): 87–106, doi:10.1016/j.comgeo.2003.07.007, hdl:1874/24413, MR 2045249

Related Articles