Computing relative neighbourhood graphs in the plane
type: Item
instance of: scholarly article
title: Computing relative neighbourhood graphs in the plane
zbMATH Open document ID: 0602.68089
DOI: 10.1016/0031-3203(86)90012-9
author: Jyrki Katajainen
author: Olli S. Nevalainen
published in: Pattern Recognition
publication date: 1986-01-01T00:00:00Z
review text: The paper presents two new algorithms for constructing the relative neighborhood graph (RNG) in two-dimensional Euclidean space. The method is to determine a supergraph for RNG which can be thinned efficiently from the extra edges.
Mathematics Subject Classification ID: 68T10
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 3972240
zbMATH Keywords: graph algorithms
zbMATH Keywords: pattern recognition
zbMATH Keywords: nearest neighbour search
MaRDI profile type: Publication
full work available at URL: 0031-3203(86)90012-9
OpenAlex ID: W2013663950
cites work: Optimal Expected-Time Algorithms for Closest Point Problems
cites work: The average performance analysis of a closest‐pair algorithm
cites work: On the average length of Delaunay triangulations
cites work: Finding Minimum Spanning Trees
cites work: Two algorithms for constructing a Delaunay triangulation
cites work: Q4187319
cites work: Delaunay triangulation and the convex hull of n points in expected linear time
cites work: On the homogeneous planar Poisson point process
cites work: Computing the relative neighborhood graph in the \(L_ 1\) and L//infinity metrics
cites work: Q5845761
cites work: Q3992847
cites work: The Relative Neighborhood Graph, with an Application to Minimum Spanning Trees
cites work: The relative neighbourhood graph of a finite planar set
cites work: Q3920971
cites work: On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
description: scientific article; zbMATH DE number 3972240