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

DOI10.1016/0031-3203(82)90070-XzbMATH Open0486.68063OpenAlexW1972165561MaRDI QIDQ1165014FDOQ1165014

Authors: 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

computational geometryDelaunay triangulationEuclidean metrictime complexityrange queries

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (6)

• The relative neighborhood graph for mixed feature variables
• \(\beta\)-skeleton depth functions and medians
• Classification by restricted random walks
• 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

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

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