An O ( n log n ) Algorithm for Rectilinear Minimal Spanning Trees
From MaRDI portal
Publication:4178506
DOI10.1145/322123.322124zbMath0395.68064OpenAlexW2035622528MaRDI QIDQ4178506
Publication date: 1979
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/322123.322124
Related Items (27)
An optimal parallel algorithm using exclusive read/writes for the rectilinear Voronoi diagram ⋮ The 1-Steiner-Minimal-Tree problem in Minkowski-spaces ⋮ A faster divide-and-conquer algorithm for constructing Delaunay triangulations ⋮ Approximation Algorithms for Buy-at-Bulk Geometric Network Design ⋮ A Scheme for Computing Minimum Covers within Simple Regions ⋮ Fast heuristic algorithms for rectilinear Steiner trees ⋮ The Steiner tree problem in orientation metrics ⋮ APPROXIMATION ALGORITHMS FOR BUY-AT-BULK GEOMETRIC NETWORK DESIGN ⋮ A scheme for computing minimum covers within simple regions ⋮ Voronoi diagrams in the moscow metric ⋮ Kinetic Voronoi diagrams and Delaunay triangulations under polygonal distance functions ⋮ An integrated approach to routing and via minimization ⋮ The rectilinear Steiner arborescence problem ⋮ Finding the largest area axis-parallel rectangle in a polygon ⋮ A heuristic for Euclidean and rectilinear Steiner problems ⋮ Stacks, queues, and deques with order-statistic operations ⋮ On approximations for constructing 1-line minimum rectilinear Steiner trees in the Euclidean plane \(\mathbb{R}^2\) ⋮ Computing a minimum-width cubic and hypercubic shell ⋮ An O(n log n) plane-sweep algorithm for \(L_ 1\) and \(L_{\infty}\) Delaunay triangulations ⋮ A fast and simple Steiner routing heuristic ⋮ \(1\)-line minimum rectilinear Steiner trees and related problems ⋮ The geometry of Minkowski spaces -- a survey. II. ⋮ Voronoi Diagrams and Their Uses ⋮ Efficient minimum spanning tree construction with Delaynay triangulation ⋮ On computing all north-east nearest neighbors in the \(L_ 1\) metric ⋮ On the maximum empty rectangle problem ⋮ Efficient algorithms for agglomerative hierarchical clustering methods
This page was built for publication: An O ( n log n ) Algorithm for Rectilinear Minimal Spanning Trees
