Relative neighborhood graphs in the Li-metric
作者：
Highlights：
•
摘要
The relative neighborhood graph of a set of n points in the plane under the L1-metric is considered. An algorithm that runs in O(nlog n) time for constructing the relative neighborhood graph based on the Delaunay triangulation is presented, improving a previously known algorithm that runs in O(n2log n) time.
论文关键词：Delaunay triangulation,Relative neighborhood graph,Analysis of algorithms,Divide-and-conquer,Scan line approach
论文评审过程：Received 1 March 1985, Available online 19 May 2003.
论文官网地址：https://doi.org/10.1016/0031-3203(85)90023-8
