Dynamic Nearest-Neighbor Searching Under General Metrics in ℝ3 and Its Applications

Let K be a compact, centrally-symmetric, strictly-convex region in ℝ³, which is a semi-algebraic set of constant complexity, i.e. the unit ball of a corresponding metric, denoted as ∥· ∥K. Let K be a set of n homothetic copies of K. This paper contains two main sets of results: (i) For a storage parameter s ∈ [n, n³], K can be preprocessed in O^∗(s) expected time into a data structure of size O^∗(s), so that for a query homothet K0 of K, an intersection-detection query (determine whether K0 intersects any member of K, and if so, report such a member) or a nearest-neighbor query (return the member of K whose ∥ · ∥K-distance from K0 is smallest) can be answered in O^∗(n/s¹/³) time; all k homothets of K intersecting K0 can be reported in additional O(k) time. In addition, the data structure supports insertions/deletions in O^∗(s/n) amortized expected time per operation. Here the O^∗(·) notation hides factors of the form n^ε, where ε > 0 is an arbitrarily small constant, and the constant of proportionality depends on ε. (ii) Let G(K) denote the intersection graph of K. Using the above data structure, breadth-first or depth-first search on G(K) can be performed in O^∗(n³/²) expected time. Combining this result with the so-called shrink-and-bifurcate technique, the reverse-shortest-path problem in a suitably defined proximity graph of K can be solved in O^∗(n⁶²/³⁹) expected time. Dijkstra’s shortest-path algorithm, as well as Prim’s MST algorithm, on a ∥· ∥K-proximity graph on n points in ℝ³, with edges weighted by ∥· ∥K, can also be performed in O^∗(n³/²) time.

Duke Scholars

Author Pankaj K. Agarwal Computer Science