Efficient minimum spanning tree construction with Delaynay triangulation

DOI10.1016/S0020-0190(01)00232-0zbMath1046.68116OpenAlexW2016523183MaRDI QIDQ1847389

Hai Zhou, William Nicholls, Narendra Shenoy

Publication date: 24 June 2003

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0020-0190(01)00232-0

zbMATH Keywords

spanning graphs

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (3)

The saga of minimum spanning trees ⋮ On approximations for constructing 1-line minimum rectilinear Steiner trees in the Euclidean plane \(\mathbb{R}^2\) ⋮ \(1\)-line minimum rectilinear Steiner trees and related problems

Cites Work

• Unnamed Item
• Unnamed Item
• An O(n log n) plane-sweep algorithm for \(L_ 1\) and \(L_{\infty}\) Delaunay triangulations
• On computing all north-east nearest neighbors in the \(L_ 1\) metric
• A sweepline algorithm for Voronoi diagrams
• Low-degree minimum spanning trees
• Priority Search Trees
• On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
• An O ( n log n ) Algorithm for Rectilinear Minimal Spanning Trees

This page was built for publication: Efficient minimum spanning tree construction with Delaynay triangulation