Computing geographic nearest neighbors using monotone matrix searching (preliminary version)

摘要

We present an &Ogr;(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 &Ogr;(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.