Rectilinear Spanning Trees Versus Bounding Boxes

D. Rautenbach


For a set $P\subseteq {\Bbb R}^2$ with $2\leq n=|P| < \infty$ we prove that ${{\rm mst}(P)\over{\rm bb}(P)} \leq{1\over\sqrt{2}}\sqrt{n}+{3\over2}$ where ${\rm mst}(P)$ is the minimum total length of a rectilinear spanning tree for $P$ and ${\rm bb}(P)$ is half the perimeter of the bounding box of $P$. Since the constant ${1\over\sqrt{2}}$ in the above bound is best-possible, this result settles a problem that was mentioned by Brenner and Vygen (Networks 38 (2001), 126-139).

Full Text: PDF