Approximate Dynamic Nearest Neighbor Searching in a Polygonal Domain

Abstract

We present efficient data structures for approximate nearest neighbor searching and approximate 2-point shortest path queries in a two-dimensional polygonal domain P with n vertices. Our goal is to store a dynamic set of m point sites S in P so that we can efficiently find a site s ∈ S closest to an arbitrary query point q. We will allow both insertions and deletions in the set of sites S. However, as even just computing the distance between an arbitrary pair of points q, s ∈ P requires a substantial amount of space, we allow for approximating the distances. Given a parameter ε > 0, we build an O(n /ε log n) space data structure that can compute a 1 + εapproximation of the distance between q and s in O(ε1/2 log n) time. Building on this, we then obtain an O(n+m/ε log n + m/ε log m) space data structure that allows us to report a site s ∈ S so that the distance between query point q and s is at most (1 + ε)-times the distance between q and its true nearest neighbor in O(ε1/2 log n + 1 /ε log n log m + 1 /ε log2 m) time. Our data structure supports updates in O(ε1/2 log n + 1/ε log n log m + 1 /ε log2 m) amortized time.