Home Bookmarks Papers Blog

Robust Proximity Search for Balls using Sublinear Space


Sariel Har-Peled, and Nirman Kumar.
$\renewcommand{\Re}{\mathbb{R}}$% Given a set of $n$ disjoint balls $b_1, \dots, b_n$ in $\Re^d$, we provide a data-structure, of near linear size, that can answer $(1\pm\varepsilon)$-approximate $k$\th-nearest neighbor queries in $O(\log n + 1/\varepsilon^d)$ time, where $k$ and $\varepsilon$ are provided at query time. If $k$ and $\varepsilon$ are provided in advance, we provide a data-structure to answer such queries, that requires (roughly) $O(n/k)$ space; that is, the data-structure has sublinear space requirement if $k$ is sufficiently large.
PDF.
Last modified: Wed Jan 22 16:15:10 CST 2014