Space-efficient approximate Voronoi diagrams

(MATH) Given a set $S$ of $n$ points in $\IR^d$, a {\em $(t,\epsilon)$-approximate Voronoi diagram (AVD)} is a partition of space into constant complexity cells, where each cell $c$ is associated with $t$ representative points of $S$, such that for any point in $c$, one of the associated representatives approximates the nearest neighbor to within a factor of $(1+\epsilon)$. Like the Voronoi diagram, this structure defines a spatial subdivision. It also has the desirable properties of being easy to construct and providing a simple and practical data structure for answering approximate nearest neighbor queries. The goal is to minimize the number and complexity of the cells in the AVD.(MATH) We assume that the dimension $d$ is fixed. Given a real parameter $\gamma$, where $2 \le \gamma \le 1/\epsilon$, we show that it is possible to construct a $(t,\epsilon)$-AVD consisting of \[O(n \epsilon^{\frac{d-1}{2}} \gamma^{\frac{3(d-1)}{2}} \log \gamma) \] cells for $t = O(1/(\epsilon \gamma)^{(d-1)/2})$. This yields a data structure of $O(n \gamma^{d-1} \log \gamma)$ space (including the space for representatives) that can answer $\epsilon$-NN queries in time $O(\log(n \gamma) + 1/(\epsilon \gamma)^{(d-1)/2})$. (Hidden constants may depend exponentially on $d$, but do not depend on $\epsilon$ or $\gamma$).(MATH) In the case $\gamma = 1/\epsilon$, we show that the additional $\log \gamma$ factor in space can be avoided, and so we have a data structure that answers $\epsilon$-approximate nearest neighbor queries in time $O(\log (n/\epsilon))$ with space $O(n/\epsilon^{d-1})$, improving upon the best known space bounds for this query time. In the case $\gamma = 2$, we have a data structure that can answer approximate nearest neighbor queries in $O(\log n + 1/\epsilon^{(d-1)/2})$ time using optimal $O(n)$ space. This dramatically improves the previous best space bound for this query time by a factor of $O(1/\epsilon^{(d-1)/2})$.(MATH) We also provide lower bounds on the worst-case number of cells assuming that cells are axis-aligned rectangles of bounded aspect ratio. In the important extreme cases $\gamma \in \{2, 1/\epsilon\}$, our lower bounds match our upper bounds asymptotically. For intermediate values of $\gamma$ we show that our upper bounds are within a factor of $O((1/\epsilon)^{(d-1)/2}\log \gamma)$ of the lower bound.