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

DOI10.1051/ITA/1987210201991MaRDI QIDQ3773333zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

Cited in

(8)

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