A divide-and-conquer algorithm for constructing relative neighborhood graph

DOI10.1007/BF02017341zbMATH Open0696.68059OpenAlexW1968399291MaRDI QIDQ911282FDOQ911282

Authors: Nen-Fu Huang 

Publication date: 1990

Published in: BIT (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02017341

Recommendations

• Computing relative neighbourhood graphs in the plane
• The Relative Neighborhood Graph, with an Application to Minimum Spanning Trees
• On constructing the relative neighborhood graphs in Euclidean k- dimensional spaces
• An almost naive algorithm for finding relative neighbourhood graphs in $L_p$ metrics
• Constructing the relative neighborhood graph in 3-dimensional Euclidean space

zbMATH Keywords

computational geometrydivide-and-conquer algorithmrelative neighborhood graph

Mathematics Subject Classification ID

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

Cites Work

• The relative neighbourhood graph of a finite planar set
• Two-Dimensional Voronoi Diagrams in the L _p -Metric
• Two algorithms for constructing a Delaunay triangulation
• Primitives for the manipulation of general subdivisions and the computation of Voronoi
• A faster divide-and-conquer algorithm for constructing Delaunay triangulations
• The Relative Neighborhood Graph, with an Application to Minimum Spanning Trees
• Computing relative neighbourhood graphs in the plane
• The region approach for computing relative neighbourhood graphs in the \(L_ p\) metric
• Optimal speeding up of parallel algorithms based upon the divide-and- conquer strategy
• An O(N log N) minimal spanning tree algorithm for N points in the plane

Cited In (4)

• New sequential and parallel algorithms for computing the \(\beta\)-spectrum
• Title not available (Why is that?)
• Computing relative neighbourhood graphs in the plane
• Constructing the relative neighborhood graph in 3-dimensional Euclidean space

This page was built for publication: A divide-and-conquer algorithm for constructing relative neighborhood graph

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