An O(N log N) minimal spanning tree algorithm for N points in the plane

DOI10.1007/BF01939358zbMath0602.68053MaRDI QIDQ1082081

Ruei-Chuan Chang, Richard Chia-Tung Lee

Publication date: 1986

Published in: BIT (Search for Journal in Brave)

zbMATH Keywords

parallel implementationtime complexityVoronoi diagramsdivide-and-conquer algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items

On a proposed divide-and-conquer minimal spanning tree algorithm ⋮ Kinetic Euclidean minimum spanning tree in the plane ⋮ A divide-and-conquer algorithm for constructing relative neighborhood graph ⋮ On the complexity of two circle connecting problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimal speeding up of parallel algorithms based upon the divide-and- conquer strategy
• Finding minimal spanning trees in a Euclidean coordinate space
• On the worst case of a minimal spanning tree algorithm for euclidean space
• A parallel algorithm for constructing minimum spanning trees
• Two algorithms for constructing a Delaunay triangulation
• On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
• Fast Algorithms for Constructing Minimal Spanning Trees in Coordinate Spaces