Computing Symmetric Angle Restricted Nearest Neighbors using Monotone Matrix Search
Yeong-Cheol Wi · Jeongbo gwahaghoe nonmunji. si'seu'tem mich i'lon · 2001
Using the Monotone Matrix Searching, we present an asymptotically optimal 0(n log n) time divide-and-conquer algorithm for solving the symmetric angle restricted nearest neighbor problem for a set of n sites in the plane under any metric, 1≤p ≤∞. This algorithm works quite well in practice even for small values of n because the associated constants in its time complexity are fairly low, and because it does not follow a focus-based approach.