Rectilinear spanning trees versus bounding boxes

被引：0

作者：

Rautenbach, D ^{[1
]}

机构：

[1] Univ Bonn, Forschungsinst Diskrete Math, D-53113 Bonn, Germany

来源：

ELECTRONIC JOURNAL OF COMBINATORICS | 2004年 / 11卷 / 01期

关键词：

D O I：

暂无

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

For a set Psubset of or equal toR(2) with 2less than or equal ton=\P\<∞ we prove that mst(P)/bb(P) ≤ 1/√2 √n +3/2 where mst( P) is the minimum total length of a rectilinear spanning tree for P and bb(P) is half the perimeter of the bounding box of P. Since the constant 1/√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).

引用

页数：4