The region approach for computing relative neighbourhood graphs in the \(L_ p\) metric

DOI10.1007/BF02247943zbMath0628.68055MaRDI QIDQ1093374

Jyrki Katajainen

Publication date: 1988

Published in: Computing (Search for Journal in Brave)

zbMATH Keywords

analysis of algorithmscomputational geometryrange searchingrelative neighbourhood graphsregion approach

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (10)

On the symmetric angle-restricted nearest neighbor problem ⋮ Rectilinear Steiner tree heuristics and minimum spanning tree algorithms using geographic nearest neighbors ⋮ A Low Arithmetic-Degree Algorithm for Computing Proximity Graphs ⋮ A linear expected-time algorithm for computing planar relative neighbourhood graphs ⋮ Survivable minimum bottleneck networks ⋮ On the angle restricted nearest neighbor problem ⋮ A divide-and-conquer algorithm for constructing relative neighborhood graph ⋮ DISTRIBUTED SPANNERS WITH BOUNDED DEGREE FOR WIRELESS AD HOC NETWORKS ⋮ Relative neighborhood graphs in three dimensions ⋮ On constructing the relative neighborhood graphs in Euclidean k- dimensional spaces

Cites Work

• Unnamed Item
• Unnamed Item
• The design of dynamic data structures
• On computing all north-east nearest neighbors in the \(L_ 1\) metric
• Computing relative neighbourhood graphs in the plane
• A linear expected-time algorithm for computing planar relative neighbourhood graphs
• Efficient worst-case data structures for range searching
• The relative neighbourhood graph of a finite planar set
• Computing the relative neighborhood graph in the \(L_ 1\) and L//infinity metrics
• The Relative Neighborhood Graph, with an Application to Minimum Spanning Trees
• Some properties of the planar Euclidean relative neighbourhood graph
• New Data Structures for Orthogonal Range Queries
• Batched dynamic solutions to decomposable searching problems
• Filtering Search: A New Approach to Query-Answering
• An almost naive algorithm for finding relative neighbourhood graphs in $L_p$ metrics
• An Elementary Proof of Nonexistence of Isometries between ℓ_p^k and ℓ_q^k
• Optimal Expected-Time Algorithms for Closest Point Problems
• Two-Dimensional Voronoi Diagrams in the L _p -Metric
• On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems

This page was built for publication: The region approach for computing relative neighbourhood graphs in the \(L_ p\) metric