Approximate range searching in higher dimension

Bernard Chazelle, Ding Liu, Avner Magen

Research output: Contribution to journalArticlepeer-review

13 Scopus citations


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 Õ(d/ 2) 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.

Original languageEnglish (US)
Pages (from-to)24-29
Number of pages6
JournalComputational Geometry: Theory and Applications
Issue number1
StatePublished - Jan 2008
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Geometry and Topology
  • Control and Optimization
  • Computational Theory and Mathematics
  • Computational Mathematics


  • Approximate range searching
  • Dimensionality reduction


Dive into the research topics of 'Approximate range searching in higher dimension'. Together they form a unique fingerprint.

Cite this