ON CONSTRUCTING THE RELATIVE NEIGHBORHOOD GRAPHS IN EUCLIDEAN K-DIMENSIONAL SPACES

Abstract

In this paper, a new algorithm for constructing the relative neighborhood graph(RNG) of an n points set in Euclidean k-dimensional space is presented, for fixed k greater-than-or-equal-to 3. The worst case running time of the algorithm is O(n2-a(k)(log n)1-a(k)), for a(k) = 2-(k+1), which is under the assumption that no three input points form an isosceles triangle. Previous algorithms need O(n2) time. Our algorithm proceeds in two phases. First, a supergraph of RNG with O(n) edges is constructed and then those edges which do not belong to RNG are eliminated.