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

Pankaj K. Agarwal, Matthew J. Katz, Micha Sharir

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 me…