The Relative Neighborhood Graph, with an Application to Minimum Spanning Trees
From MaRDI portal
Publication:3028354
DOI10.1145/2402.322386zbMath0625.68047OpenAlexW1968721698MaRDI QIDQ3028354
Publication date: 1983
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2402.322386
Related Items (31)
Population-driven urban road evolution dynamic model ⋮ Optimal and suboptimal robust algorithms for proximity graphs ⋮ Computing relative neighbourhood graphs in the plane ⋮ A linear-time construction of the relative neighborhood graph from the Delaunay triangulation ⋮ Rectilinear Steiner tree heuristics and minimum spanning tree algorithms using geographic nearest neighbors ⋮ The region approach for computing relative neighbourhood graphs in the \(L_ p\) metric ⋮ A linear-time construction of the relative neighborhood graph within a histogram ⋮ The expected size of some graphs in computational geometry ⋮ A Low Arithmetic-Degree Algorithm for Computing Proximity Graphs ⋮ A linear expected-time algorithm for computing planar relative neighbourhood graphs ⋮ A simple linear-time algorithm for computing the ring and MST of unimodal polygons ⋮ Complexity, convexity, and unimodality ⋮ $$\beta $$-skeletons for a Set of Line Segments in $$R^2 $$ ⋮ An almost naive algorithm for finding relative neighbourhood graphs in $L_p$ metrics ⋮ On the angle restricted nearest neighbor problem ⋮ A divide-and-conquer algorithm for constructing relative neighborhood graph ⋮ Coloring certain proximity graphs ⋮ Computing the relative neighborhood graph in the \(L_ 1\) and L//infinity metrics ⋮ A new distributed topology control algorithm based on optimization of delay and energy in wireless networks ⋮ Constructing the relative neighborhood graph in 3-dimensional Euclidean space ⋮ Local solutions for global problems in wireless networks ⋮ The \(\gamma\)-neighborhood graph ⋮ Relative neighborhood graphs in three dimensions ⋮ Fast algorithms for computing \(\beta\)-skeletons and their relatives. ⋮ An O(n log n) plane-sweep algorithm for \(L_ 1\) and \(L_{\infty}\) Delaunay triangulations ⋮ Growing spanning trees in plasmodium machines ⋮ On constructing the relative neighborhood graphs in Euclidean k- dimensional spaces ⋮ An algorithm for geometric minimum spanning trees requiring nearly linear expected time ⋮ An optimal algorithm for computing the minimum vertex distance between two crossing convex polygons ⋮ New sequential and parallel algorithms for computing the \(\beta\)-spectrum ⋮ Finding the minimum vertex distance between two disjoint convex polygons in linear time
This page was built for publication: The Relative Neighborhood Graph, with an Application to Minimum Spanning Trees
