×

Rectilinear spanning trees versus bounding boxes. (English) Zbl 1060.05023

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 U. Brenner and J. Vygen [Networks 38, 126–139 (2001; Zbl 0990.68101)].

MSC:

05C05 Trees

Citations:

Zbl 0990.68101
PDFBibTeX XMLCite
Full Text: EuDML EMIS