Relative neighborhood graphs in three dimensions

DOI10.1016/0925-7721(92)90017-MzbMath0764.68105OpenAlexW4213246238MaRDI QIDQ1200909

Pankaj K. Agarwal, Ji{ří} Matoušek

Publication date: 16 January 1993

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0925-7721(92)90017-m

zbMATH Keywords

arrangementsrandomized algorithmgeometric graphspattern matchingrandom samplingrelative neighborhood graphclosest pairs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (4)

A linear-time construction of the relative neighborhood graph from the Delaunay triangulation ⋮ Sigma-local graphs ⋮ Empty region graphs ⋮ Computing Euclidean bottleneck matchings in higher dimensions

Cites Work

• Unnamed Item
• A deterministic view of random sampling and its use in geometry
• Combinatorial complexity bounds for arrangements of curves and spheres
• 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
• The relative neighbourhood graph of a finite planar set
• Constructing the relative neighborhood graph in 3-dimensional Euclidean space
• Euclidean minimum spanning trees and bichromatic closest pairs
• Farthest neighbors, maximum spanning trees and related problems in higher dimensions
• New applications of random sampling in computational geometry
• Applications of random sampling in computational geometry. II
• The Relative Neighborhood Graph, with an Application to Minimum Spanning Trees
• Some properties of the planar Euclidean relative neighbourhood graph
• A Randomized Algorithm for Closest-Point Queries
• On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems

This page was built for publication: Relative neighborhood graphs in three dimensions