Computing a (1+ε)-Approximate Geometric Minimum-Diameter Spanning Tree

被引：0

作者：

Michael J. Spriggs

J. Mark Keil

Sergei Bespamyatnikh

Michael Segal

Jack Snoeyink

机构：

[1] School of Computer Science,

[2] University of Waterloo,undefined

[3] 200 University Avenue West,undefined

[4] Waterloo,undefined

[5] Ontario,undefined

[6] N2L 3G1,undefined

[7] Department of Computer Science,undefined

[8] University of Saskatchewan,undefined

[9] Saskatoon,undefined

[10] Saskatchewan,undefined

[11] S7N 5A9,undefined

[12] Department of Computer Science,undefined

[13] Duke University,undefined

[14] Box 90129,undefined

[15] Durham,undefined

[16] NC 27708,undefined

[17] Communication Systems Engineering Department,undefined

[18] Ben-Gurion University of the Negev,undefined

[19] Beer-Sheva,undefined

[20] 84105,undefined

[21] Department of Computer Science,undefined

[22] University of North Carolina at Chapel Hill,undefined

[23] Chapel Hill,undefined

[24] NC 27599-3175,undefined

来源：

Algorithmica | 2004年 / 38卷

关键词：

Minimum diameter spanning tree; Approximation algorithm; Geometric graph;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

Given a set P of points in the plane, a geometric minimum-diameter spanning tree (GMDST) of P is a spanning tree of P such that the longest path through the tree is minimized. For several years, the best upper bound on the time to compute a GMDST was cubic with respect to the number of points in the input set. Recently, Timothy Chan introduced a subcubic time algorithm. In this paper we present an algorithm that generates a tree whose diameter is no more than (1 + ε) times that of a GMDST, for any ε > 0. Our algorithm reduces the problem to several grid-aligned versions of the problem and runs within time $O(ε-3+ n) and space O(n).

引用

页码：577 / 589

页数：12

共 17 条

[1] Callahan P.(1995)A decomposition of multidimensional point sets with applications to k-nearest neighbors and n-body potential fields Journal of the ACM 42 67-90
[2] Kosaraju R.(1980)Complexity of spanning tree problems, I European Journal of Operational Research 5 346-352
[3] Camerini P.M.(1996)Performance optimization of VLSI interconnection layout Integration: the VLSI Journal 21 1-94
[4] Galbiati G.(1995)On the minimum diameter spanning tree problem Information Processing Letters 53 109-111
[5] Maffioli F.(1991)Minimum diameter spanning trees and related problems SIAM Journal on Computing 20 987-997
[6] Cong J.(1979)An algorithmic approach to network location problems, I: the p-centers SIAM Journal on Applied Mathematics 37 513-537
[7] He L.(undefined)undefined undefined undefined undefined-undefined
[8] Koh C.(undefined)undefined undefined undefined undefined-undefined
[9] Madden P.(undefined)undefined undefined undefined undefined-undefined
[10] Hassin R.(undefined)undefined undefined undefined undefined-undefined

← 1 2 →