Rectilinear spanning trees versus bounding boxes

MaRDI QIDQ1773175zbMATH OpenFDO

Authors Dieter Rautenbach

Publication date 25 April 2005

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/124418, http://www.emis.de/journals/EJC/Volume_11/Abstracts/v11i1n12.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

Trees (05C05)

Review text

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)].

Recommendations

• Some upper bounds for minimal trees
• Publication:4505722
• Shortest trees and Steiner trees with rectilinear distances
• The minimal spanning tree and the upper box dimension
• scientific article; zbMATH DE number 3912403

This page was built for publication: Rectilinear spanning trees versus bounding boxes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1773175)