1987 · 44 citations · 6 references
ComputingComputer ScienceAlgorithmsComputational GeometryData StructuresDelaunay TriangulationsGraph AlgorithmsIntersection DetectionNearest Neighbor SearchNeighborhood StructureDelaunay Triangulation AlgorithmsMetric Space SearchNeighborhood Graph ConstructionTriangulation AlgorithmsUnion-find Data Structures
Two new algorithms finding relative neighborhood graph RNG(V) for a set V of n points are presented. The first algorithm solves this problem for input points in (R2,Lp) metric space in time O(n a(n,n)) if the Delaunay triangulation DT(V) is given. This time performance is achieved due to attractive and natural application of FIND-UNION data structure to represent so-called elimination forest of edges in DT(V). The second algorithm solves the relative neighborhood graph problem in (Rd,Lp), 1
6
Algorithms in Combinatorial Geometry.
Jacob E. Goodman, Herbert Edelsbrunner · American Mathematical Monthly · 1989 · 1.8K citations
An improved equivalence algorithm
Bernard A. Galler, Michael Fisher · Communications of the ACM · 1964 · 310 citations · Full text