A note on bisecting minimum spanning trees

Authors:

Abstract
Let A be a finite set of points in a Euclidean space Er and M a minimum spanning tree (MST) for A, regarded as a subset of Er. If A′ ⊂ Er is a finite subset of M, then M is a spanning tree for A ∪ A′, but in general M will no longer be an MST. However, if A′ is chosen to be the set of all the midpoints of the line segments of M, then M will be an MST for A ∪ A′. Examples are given in which at least |A| ‐ 1 points must be adjoined to avoid destroying the MST.

This publication has 3 references indexed in Scilit: