Computing the relative neighborhood graph in the \(L_ 1\) and L//infinity metrics

DOI10.1016/0031-3203(82)90070-XzbMath0486.68063OpenAlexW1972165561MaRDI QIDQ1165014

Joseph O'Rourke

Publication date: 1982

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

Full work available at URL: https://doi.org/10.1016/0031-3203(82)90070-x

zbMATH Keywords

time complexitycomputational geometryDelaunay triangulationEuclidean metricrange queries

Mathematics Subject Classification ID

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

Related Items (6)

β-Skeleton depth functions and medians ⋮ Computing relative neighbourhood graphs in the plane ⋮ The region approach for computing relative neighbourhood graphs in the \(L_ p\) metric ⋮ An almost naive algorithm for finding relative neighbourhood graphs in $L_p$ metrics ⋮ Classification by restricted random walks ⋮ The relative neighborhood graph for mixed feature variables

Cites Work

• Unnamed Item
• Multidimensional divide-and-conquer
• Efficient worst-case data structures for range searching
• The relative neighbourhood graph of a finite planar set
• The Relative Neighborhood Graph, with an Application to Minimum Spanning Trees
• An Elementary Proof of Nonexistence of Isometries between ℓ_p^k and ℓ_q^k
• Two-Dimensional Voronoi Diagrams in the L _p -Metric
• Voronoui Diagrams in $L_1 (L_\infty )$ Metrics with 2-Dimensional Storage Applications
• Multidimensional Searching Problems
• Some Upper Bounds on Error Probability for Multiclass Pattern Recognition

This page was built for publication: Computing the relative neighborhood graph in the \(L_ 1\) and L//infinity metrics