Rectilinear Spanning Trees Versus Bounding Boxes
Rectilinear Spanning Trees Versus Bounding Boxes
复制标题
直线生成树与边界框
DOI：
--
复制
发表时间：
2004
影响因子：
0.7
通讯作者：
D. Rautenbach
中科院分区：
文献类型：
--
作者：
D. Rautenbach
对于集合 P ⊆ R2 且 2 ≤ n = |P | < ∞ 我们证明 mst(P ) bb(P ) ≤ 1 √2 √ n + 32 其中 mst(P ) 是 P 的直线生成树的最小总长度，bb(P ) 是 P 的边界框周长的一半。由于上述界限中的常数 1 √ 2 是最佳可能的，因此该结果解决了 Brenner 和 Vygen 提到的问题 (Networks 38 (2001), 126-139)。
For a set P ⊆ R2 with 2 ≤ n = |P | < ∞ we prove that mst(P ) bb(P ) ≤ 1 √2 √ n + 32 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).