標題: ON CONSTRUCTING THE RELATIVE NEIGHBORHOOD GRAPHS IN EUCLIDEAN K-DIMENSIONAL SPACES
作者: SU, TH
CHANG, RC
資訊科學與工程研究所
Institute of Computer Science and Engineering
關鍵字: ANALYSIS OF ALGORITHM;COMPUTATIONAL GEOMETRY;INVERSION;RELATIVE NEIGHBORHOOD GRAPH;GEOGRAPHICAL NEIGHBORHOOD GRAPH
公開日期: 1991
摘要: 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.
URI: http://hdl.handle.net/11536/3884
http://dx.doi.org/10.1007/BF02239166
ISSN: 0010-485X
DOI: 10.1007/BF02239166
期刊: COMPUTING
Volume: 46
Issue: 2
起始頁: 121
結束頁: 130
Appears in Collections:Articles