The Relative Neighborhood Graph, with an Application to Minimum Spanning Trees

DOI10.1145/2402.322386MaRDI QIDQ3028354zbMATH OpenOpenAlexFDO

Authors Kenneth J. Supowit

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

zbMATH Keywords

graph algorithmsminimum spanning treerelative neighborhood graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• An almost naive algorithm for finding relative neighbourhood graphs in L_p metrics
• Relative neighborhood graphs in three dimensions
• Constructing the relative neighborhood graph in 3-dimensional Euclidean space
• scientific article; zbMATH DE number 742948
• Computing relative neighbourhood graphs in the plane

Cited in

(36)

• The relative neighborhood graph for mixed feature variables
• Finding the minimum vertex distance between two disjoint convex polygons in linear time
• Computing relative neighbourhood graphs in the plane
• The region approach for computing relative neighbourhood graphs in the \(L_ p\) metric
• The expected size of some graphs in computational geometry
• 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
• Computing the relative neighborhood graph in the \(L_ 1\) and L//infinity metrics
• Constructing the relative neighborhood graph in 3-dimensional Euclidean space
• The \(\gamma\)-neighborhood graph
• Relative neighborhood graphs in three dimensions
• Time-optimal proximity graph computations on enhanced meshes
• 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
• An algorithm for geometric minimum spanning trees requiring nearly linear expected time
• Optimal and suboptimal robust algorithms for proximity graphs
• New sequential and parallel algorithms for computing the \(\beta\)-spectrum
• Population-driven urban road evolution dynamic model
• Local solutions for global problems in wireless networks
• -skeletons for a set of line segments in R^2
• Complexity, convexity, and unimodality
• Growing spanning trees in plasmodium machines
• An almost naive algorithm for finding relative neighbourhood graphs in L_p metrics
• scientific article; zbMATH DE number 4080989 (Why is no real title available?)
• A low arithmetic-degree algorithm for computing proximity graphs
• A new distributed topology control algorithm based on optimization of delay and energy in wireless networks
• scientific article; zbMATH DE number 742948 (Why is no real title available?)
• A linear-time construction of the relative neighborhood graph within a histogram
• Fast algorithms for computing -skeletons and their relatives.
• An O(n log n) plane-sweep algorithm for \(L_ 1\) and \(L_{\infty}\) Delaunay triangulations
• On constructing the relative neighborhood graphs in Euclidean k- dimensional spaces
• An optimal algorithm for computing the minimum vertex distance between two crossing convex polygons
• On the angle restricted nearest neighbor problem
• A divide-and-conquer algorithm for constructing relative neighborhood graph
• Coloring certain proximity graphs
• The relative neighbourhood graph is a part of every \(30^\circ \)-triangulation

This page was built for publication: The Relative Neighborhood Graph, with an Application to Minimum Spanning Trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3028354)