A note on relative neighborhood graphs
Jerzy W. Jaromczyk, Mirosław Kowaluk · 1987
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