Approximate range searching in higher dimension

Applying standard dimensionality reduction techniques, we show how to perform approximate range searching in higher dimension while avoiding the curse of dimensionality. Given n points in a unit ball in Rd, an approximate halfspace range query counts (or reports) the points in a query halfspace; the qualifier “approximate” indicates that points within distance ε of the boundary of the halfspace might be misclassified. Allowing errors near the boundary has a dramatic effect on the complexity of the problem. We give a solution with query time and dnO(ε−2) storage. For an exact solution with comparable query time, one needs roughly Ω(nd) storage. In other words, an approximate answer to a range query lowers the storage requirement from exponential to polynomial. We generalize our solution to polytope/ball range searching.