Dynamic Nearest-Neighbor Searching Under General Metrics in ${\mathbb{R}}^3$ and Its Applications

Abstract

Let $K$ be a compact, centrally-symmetric, strictly-convex region in ${\mathbb{R}}^3$, which is a semi-algebraic set of constant complexity, i.e. the unit ball of a corresponding metric, denoted as $\Vert \cdot {\Vert }_K$. Let $\mathcal{K}$ be a set of $n$ homothetic copies of $K$. This paper contains two main sets of results: (i) For a storage parameter $s\in [n,n^3]$, $\mathcal{K}$ can be preprocessed in $O^{\ast }(s)$ expected time into a data structure of size $O^{\ast }(s)$, so that for a query homothet $K_0$ of $K$, an intersection-detection query (determine whether $K_0$ intersects any member of $\mathcal{K}$, and if so, report such a member) or a nearest-neighbor query (return the member of $\mathcal{K}$ whose $\Vert \cdot {\Vert }_K$-distance from $K_0$ is smallest) can be answered in $O^{\ast }(n/s^{1/3})$ time; all $k$ homothets of $\mathcal{K}$ intersecting $K_0$ can be reported in additional $O(k)$ time. In addition, the data structure supports insertions/deletions in $O^{\ast }(s/n)$ amortized expected time per operation. Here the $O^{\ast }(\cdot )$ notation hides factors of the form $n^{\epsilon }$, where $\epsilon >0$ is an arbitrarily small constant, and the constant of proportionality depends on $\epsilon$. (ii) Let $\mathcal{G}(\mathcal{K})$ denote the intersection graph of $\mathcal{K}$. Using the above data structure, breadth-first or depth-first search on $\mathcal{G}(\mathcal{K})$ can be performed in $O^{\ast }(n^{3/2})$ 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 $\mathcal{K}$ can be solved in $O^{\ast }(n^{62/39})$ expected time. Dijkstra's shortest-path algorithm, as well as Prim's MST algorithm, on a $\Vert \cdot {\Vert }_K$-proximity graph on $n$ points in ${\mathbb{R}}^3$, with edges weighted by $\Vert \cdot {\Vert }_K$, can also be performed in $O^{\ast }(n^{3/2})$ time.