Computing relative neighbourhood graphs in the plane

DOI10.1016/0031-3203(86)90012-9zbMath0602.68089OpenAlexW2013663950MaRDI QIDQ1082094

Jyrki Katajainen, Olli S. Nevalainen

Publication date: 1986

Published in: Pattern Recognition (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0031-3203(86)90012-9

zbMATH Keywords

pattern recognitiongraph algorithmsnearest neighbour search

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Pattern recognition, speech recognition (68T10)

Related Items (10)

Computing relative neighbourhood graphs in the plane ⋮ The region approach for computing relative neighbourhood graphs in the \(L_ p\) metric ⋮ A linear expected-time algorithm for computing planar relative neighbourhood graphs ⋮ An almost naive algorithm for finding relative neighbourhood graphs in $L_p$ metrics ⋮ A divide-and-conquer algorithm for constructing relative neighborhood graph ⋮ An optimal algorithm for constructing oriented Voronoi diagrams and geograph neighborhood graphs ⋮ Solving the Euclidean bottleneck matching problem by \(k\)-relative neighborhood graphs ⋮ Solving the Euclidean bottleneck biconnected edge subgraph problem by 2- relative neighborhood graphs ⋮ Relative neighborhood graphs in three dimensions ⋮ On constructing the relative neighborhood graphs in Euclidean k- dimensional spaces

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Delaunay triangulation and the convex hull of n points in expected linear time
• On the average length of Delaunay triangulations
• Computing relative neighbourhood graphs in the plane
• The relative neighbourhood graph of a finite planar set
• Computing the relative neighborhood graph in the \(L_ 1\) and L//infinity metrics
• On the homogeneous planar Poisson point process
• The Relative Neighborhood Graph, with an Application to Minimum Spanning Trees
• The average performance analysis of a closest‐pair algorithm
• Two algorithms for constructing a Delaunay triangulation
• Optimal Expected-Time Algorithms for Closest Point Problems
• On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
• Finding Minimum Spanning Trees

This page was built for publication: Computing relative neighbourhood graphs in the plane