Transitions in geometric minimum spanning trees
type: Item
instance of: scholarly article
title: Transitions in geometric minimum spanning trees
zbMATH Open document ID: 0764.05022
DOI: 10.1007/BF02293049
author: Subhash Suri
author: Clyde l. Monma
published in: Discrete \& Computational Geometry
publication date: 1993-01-16T00:00:00Z
review text: 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…
reviewed by: Richard G. Wilson
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C12
zbMATH DE Number: 93448
zbMATH Keywords: labelled tree
zbMATH Keywords: \(\varepsilon\)-perturbation
zbMATH Keywords: minimum spanning tree
zbMATH Keywords: cost
zbMATH Keywords: Euclidean distance
zbMATH Keywords: topologically equivalent
zbMATH Keywords: sensitivity measure
MaRDI profile type: Publication
cites work: Some dynamic computational geometry problems
cites work: New upper bounds for neighbor searching
cites work: Optimal attack and reinforcement of a network
cites work: On a Multidimensional Search Technique and Its Application to the Euclidean One-Centre Problem
cites work: Q3772828
cites work: A Fast Parametric Maximum Flow Algorithm and Applications
cites work: The 1-steiner tree problem
cites work: Parametric Combinatorial Computing and a Problem of Program Module Distribution
cites work: Parametric stable marriage and minimum cuts
cites work: Fast Algorithms for Finding Nearest Common Ancestors
cites work: Computing Euclidean maximum spanning trees
cites work: Selected Applications of Minimum Cuts in Networks
cites work: A Cut Approach to the Rectilinear Distance Facility Location Problem
cites work: A data structure for dynamic trees
cites work: On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
full work available at URL: https://doi.org/10.1007/bf02293049
OpenAlex ID: W2088839217
description: scientific article; zbMATH DE number 93448