An almost naive algorithm for finding relative neighbourhood graphs in L_p metrics

DOI10.1051/ITA/1987210201991zbMATH Open0634.68030OpenAlexW102387838MaRDI QIDQ3773333FDOQ3773333

Authors: Jyrki Katajainen, Olli S. Nevalainen 

Publication date: 1987

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/92284

Recommendations

• The Relative Neighborhood Graph, with an Application to Minimum Spanning Trees
• The region approach for computing relative neighbourhood graphs in the \(L_ p\) metric
• Relative neighborhood graphs in three dimensions
• On constructing the relative neighborhood graphs in Euclidean k- dimensional spaces
• scientific article; zbMATH DE number 742948

zbMATH Keywords

algorithmrelative neighbourhood graph\(L_ p\) metric

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Extremal problems in graph theory (05C35)

Cites Work

• The relative neighbourhood graph of a finite planar set
• On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
• Efficient worst-case data structures for range searching
• The Relative Neighborhood Graph, with an Application to Minimum Spanning Trees
• Title not available (Why is that?)
• Title not available (Why is that?)
• Computing relative neighbourhood graphs in the plane
• A linear expected-time algorithm for computing planar relative neighbourhood graphs
• Computing the relative neighborhood graph in the \(L_ 1\) and L//infinity metrics
• Title not available (Why is that?)
• Title not available (Why is that?)
• An Elementary Proof of Nonexistence of Isometries between ℓ_p^k and ℓ_q^k

Cited In (8)

• The Relative Neighborhood Graph, with an Application to Minimum Spanning Trees
• Neighborhood principle driven ICF algorithm and graph distance calculations
• Practical Construction of k-Nearest Neighbor Graphs in Metric Spaces
• The relative neighborhood graph for mixed feature variables
• 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
• A divide-and-conquer algorithm for constructing relative neighborhood graph

This page was built for publication: An almost naive algorithm for finding relative neighbourhood graphs in $L_p$ metrics

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