Computing geographic nearest neighbors using monotone matrix searching (preliminary version)
Young Cheul Wee, Seth Chaiken, Dan E. Willard · 1990
We present an Ο(N log2 N) divide-and-conquer algorithm for solving the all pairs geographic nearest neighbor problem (GNN) for a set of N sites in the plane under any Lp metric, 1 ≤ p ≥ ∞. This algorithm uses the monotone matrix searching technique of Aggarwal et. al. In addition, our method yields an Ο(N logd-1 N) expected time algorithm for the d-dimensional GNN problem. We also discuss the applications of GNN approach to rectilinear Steiner trees.