Robust Proximity Search for Balls Using Sublinear Space
Sariel Har-Peled, Nirman Kumar · Algorithmica · 2016
Given a set of n disjoint balls $$b_1, \dots , b_n$$ in $$\mathrm{I\! R}^d$$ , we provide a data structure of near linear size that can answer $$(1\pm {\varepsilon })$$ -approximate kth-nearest neighbor queries on the balls in $$O(\log n + 1/{\varepsilon }^d)$$ time, where k and $${\varepsilon }$$ may be provided at query time. If k and $${\varepsilon }$$ are provided in advance, we provide a data structure to answer such queries requiring O(n / k) space; that is, the data structure requires sublinear space if k is sufficiently large.