Transitions in geometric minimum spanning trees (Q1199130)

A minimum spanning tree of a labelled subset \(S\) of \(\mathbb{R}^ d\), denoted \(\text{MST}(S)\), is a minimum cost tree connecting the elements of \(S\), where the cost of an edge is the Euclidean distance between its end- points. Say that \(\text{MST}(S\cup\{p\})\) and \(\text{MST}(S\cup\{q\})\) are topologically equivalent if they are isomorphic as labelled graphs. The principal results of this article can be summarised as follows: (1) When \(d\geq 3\), it is shown that at least \(\Omega(n^ d)\) and at most \(O(n^{2d})\) topologically distinct minimum spanning trees \(\text{MST}(S\cup\{x\})\) can arise as \(x\) varies over \(\mathbb{R}^ d\); when \(d=2\), the upper bound is \(O(n^ 2)\). (2) For \(d\geq 3\), there is an \(O(n^{2d})\)-time algorithm for computing a subdivision of \(\mathbb{R}^ d\) into maximally connected cells such that for all \(x\) in some cell, the minimum spanning trees \(\text{MST}(S\cup\{x\})\) are all topologically equivalent. When \(d<3\), the algorithm runs in time \(O(n^ d)\). (3) Given a set \(S\) of \(n\) (fixed) points in \(\mathbb{R}^ d\) and a tree \(T\) with vertices \(S\cup\{x\}\), where \(x\) is a variable point, there is an \(O(n)\)- time algorithm for deciding whether there is a point \(p\in\mathbb{R}^ d\) for which \(\text{MST}(S\cup\{p\})\) and \(T\) are topologically equivalent. (4) A finite set \(S'\) in \(\mathbb{R}^ d\) is an \(\varepsilon\)-perturbation of \(S\) if there is a one-to-one map \(f\) of \(S'\) onto \(S\) such that for each point \(x\in S'\), the distance of \(x\) from \(f(x)\) is less than \(\varepsilon\). The sensitivity measure of \(S\) is the supremum of all \(\varepsilon\) for which all \(\varepsilon\)-perturbations of \(S\) have topologically equivalent minimum spanning trees. It is shown that in \(\mathbb{R}^ 2\), there is an \(O(n\log n)\)-time algorithm for determining the sensitivity measure of a set of points \(S\). (5) In \(\mathbb{R}^ 2\), it is shown that a tree \(T\) and \(n\) vertices can be realised as the minimum spanning tree of a set of \(n\) points iff the degree of each vertex of \(T\) is less than or equal to 5. The final section of the paper contains some open problems.