Geometric Range Searching and Its Relatives

377 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Approximate Nearest Subspace Search with Applications to Pattern Recognition (2007, methodology): “For example, for a database containing n points in R d , exact nearest neighbor can be found by transforming the problem to a point location problem in an arrangement of hyperplanes [1], which can in turn be solved using Meiser’s ray shooting algorithm in time O ( d 5 log n ) [14].”
A semi-algebraic version of Zarankiewicz's problem (2014, methodology): “By combining this technique with the standard theory of random sampling [1, 2, 13], one can obtain the following lemma which will be used in the next section.”
BICO: BIRCH Meets Coresets for k-Means Clustering (2013, methodology): “By using range query data structures, N(m) = O(logd−1m) can be achieved at the cost of O(m logd−1m) additional space [3].”