O(N LOG N) ALGORITHM FOR RECTILINEAR MINIMAL SPANNING TREES

被引：79

作者：

HWANG, FK

机构：

[1] Bell Laboratories, Murray Hill, NJ 07974

来源：

JOURNAL OF THE ACM | 1979年 / 26卷 / 02期

关键词：

minimal spanning tree; rectdmear distance; Voronot diagram;

D O I：

10.1145/322123.322124

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

Let P be a set of pomts m the plane with rectdmear distance An O(n log n) algonthm for the construeUon ofa Voronot diagram for P ts gwen By using prewously known results, a mmmaal spammuag tree for P can be derived from a Voronot diagram for P m hnear tmae. © 1979, ACM. All rights reserved.

引用

页码：177 / 182

页数：6

共 7 条

[1]

AHO AV, 1974, DESIGN ANAL COMPUTER, P470

[2]

BORUVKA O, 1926, PRACE MORASKE PRIDOV, V3

[3]

CHERITON R, 1976, SIAM J COMPTNG, V5, P724

[4]

Choquet G., 1938, CR HEBD ACAD SCI, V206, P310

[5]

Kruskal J.B., 1956, P AM MATH SOC, V7, P3, DOI [10.2307/2033241, DOI 10.1090/S0002-9939-1956-0078686-7, 10.1090/S0002-9939-1956-0078686-7]

[6] SHORTEST CONNECTION NETWORKS AND SOME GENERALIZATIONS [J].

PRIM, RC .

BELL SYSTEM TECHNICAL JOURNAL, 1957, 36 (06) :1389-1401

[7]

Shamos M. I., 1975, 16TH P IEEE S F COMP, P151, DOI DOI 10.1109/SFCS.1975.8

← 1 →