Ruixiong Tian, Zhe Xiang, et al.
Qinghua Daxue Xuebao/Journal of Tsinghua University
We present an O(n log n) time divide-and-conquer algorithm for solving the symmetric angle-restricted nearest neighbor (SARNN) problem for a set of n points in the plane under any Lp metric, 1 ≤ p ≤ ∞. This algorithm is asymptotically optimal (within a multiplicative constant) for any constant p ≥ 1. © 2004 Published by Elsevier B.V.