Rectilinear spanning trees versus bounding boxes (Q1773175)

Summary: For a set \(P\subseteq {\mathbb R}^2\) with \(2\leq n=|P|<\infty\) we prove that \(\frac {\text{mst}(P)} {\text{bb}(P)} \leq \frac {1} {\sqrt{2}} \sqrt{n}+ \frac {3}{2}\) where \(\text{mst}(P)\) is the minimum total length of a rectilinear spanning tree for \(P\) and \(\text{bb}(P)\) is half the perimeter of the bounding box of \(P\). Since the constant \(\frac {1}{\sqrt{2}}\) in the above bound is best possible, this result settles a problem that was mentioned by \textit{U. Brenner} and \textit{J. Vygen} [Networks 38, 126--139 (2001; Zbl 0990.68101)].