ANN queries: covering Voronoi diagram with hyperboxes

Given a set $S$ of $n$ points in $d$-dimensional Euclidean metric space $X$ and a small positive real number $ϵ$, we present an algorithm to preprocess $S$ and answer queries that require finding a set $S^{\mathrm{\prime }}\subseteq S$ of $ϵ$-approximate nearest neighbors (ANNs) to a given query point $q \in X$\mathrm{.}Thefollowingarethecharacteristicsofpointsbelongingtoset$S’$:

• $\mathrm{\forall }s\in S^{\mathrm{\prime }}$, $\mathrm{\exists }$ a point $p\in X$ such that $|pq| \le \epsilon$andthenearestneighborof$p$is$s$, and
• $\mathrm{\exists }$ a $s^{\mathrm{\prime }}\in S^{\mathrm{\prime }}$ such that $s^{\mathrm{\prime }}$ is a nearest neighbor of $q$. During the preprocessing phase, from the Voronoi diagram of $S$ we construct a set of box trees of size $O(4^d\frac{V}{\delta }(\frac{\pi }{ϵ}{)}^{d-1})$ which facilitate in querying ANNs of any input query point in $O(\frac{1}{d}lg \frac{V}{\delta} + (\frac{\pi}{\epsilon})^{d-1})$time\mathrm{.}Here$\delta$equalsto$(\frac{\epsilon}{2\sqrt{d}})^d$,and$V$ is the volume of a large bounding box that contains all the points of set $S$. The average case cardinality of $S^{\mathrm{\prime }}$ is shown to rely on $S$ and $ϵ$.