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

DOI10.1007/BF02017341zbMath0696.68059OpenAlexW1968399291MaRDI QIDQ911282

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

zbMATH Keywords

computational geometrydivide-and-conquer algorithmrelative neighborhood graph

Mathematics Subject Classification ID

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

Related Items (1)

New sequential and parallel algorithms for computing the \(\beta\)-spectrum

Cites Work

• 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
• Computing relative neighbourhood graphs in the plane
• The region approach for computing relative neighbourhood graphs in the \(L_ p\) metric
• A faster divide-and-conquer algorithm for constructing Delaunay triangulations
• The relative neighbourhood graph of a finite planar set
• The Relative Neighborhood Graph, with an Application to Minimum Spanning Trees
• Primitives for the manipulation of general subdivisions and the computation of Voronoi
• Two algorithms for constructing a Delaunay triangulation
• Two-Dimensional Voronoi Diagrams in the L _p -Metric

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