COMPUTING THE K-RELATIVE NEIGHBORHOOD GRAPHS IN EUCLIDEAN PLANE

Abstract

In this paper, we will propose an O(n5/3log n) algorithm to construct the k-relative neighborhood graph of a n points set in Euclidean plane, for fixed k. Based on this result, the Euclidean bottleneck matching problem can also be solved in the same time complexity. The k-relative neighborhood graph is a generalization of the relative neighborhood graph.