The relative neighbourhood graph of a finite planar set

1980/01/01 by Godfried T. Toussaint · 8 citations
Computer Science · Engineering · Mathematics · #Algorithm #Combinatorics #Computational Geometry and Mesh Generation #Computational geometry #Computer science #Delaunay triangulation #Digital Image Processing Techniques #Discrete mathematics #Geometry #Graph #Mathematics #Neighbourhood (mathematics) #Planar #Planar graph #Robotics and Sensor-Based Localization #Spanning tree #Voronoi diagram

paper · doi:10.1016/0031-3203(80)90066-7

crossref issued 1980/01/01 · crossref published 1980/01/01 · crossref published-print 1980/01/01 · openalex publication_date 1980/01/01 · crossref created 2003/06/30 · crossref deposited 2019/03/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/23 · crossref indexed 2026/08/07

Citations

• Closest-point problems

Cited by

• A linear-time construction of the relative neighborhood graph from the Delaunay triangulation
• Computing the relative neighborhood graph in the L1 and L∞ metrics
• Constructing the relative neighborhood graph in 3-dimensional Euclidean space
• Relative neighborhood graphs in the Li-metric
• A linear expected-time algorithm for computing planar relative neighbourhood graphs
• Algorithms for computation of relative neighbourhood graph
• The Relative Neighborhood Graph, with an Application to Minimum Spanning Trees
• Relative neighborhood graph [wikipedia]