Computing the k-relative neighborhood graphs in Euclidean plane
作者：
Highlights：
•
摘要
In this paper, we will propose an O(n53logn) 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.
论文关键词：Computational geometry,Pattern recognition,Relative neighborhood graph,Geographical neighborhood graph,Bottleneck matching
论文评审过程：Received 6 June 1989, Revised 25 May 1990, Accepted 2 August 1990, Available online 19 May 2003.
论文官网地址：https://doi.org/10.1016/0031-3203(91)90065-D
