On approximate range counting and depth

Peyman Afshani, Timothy M. Chan

Research output: Contribution to journalArticlepeer-review


We improve the previous results by Aronov and Har-Peled (SODA'05) and Kaplan and Sharir (SODA'06) and present a randomized data structure of O(n) expected size which can answer 3D approximate halfspace range counting queries in $O(\log{n\over k})$ expected time, where k is the actual value of the count. This is the first optimal method for the problem in the standard decision tree model; moreover, unlike previous methods, the new method is Las Vegas instead of Monte Carlo. In addition, we describe new results for several related problems, including approximate Tukey depth queries in 3D, approximate regression depth queries in 2D, and approximate linear programming with violations in low dimensions.

Original languageEnglish (US)
Pages (from-to)3-21
Number of pages19
JournalDiscrete and Computational Geometry
Issue number1
StatePublished - Jul 2009
Externally publishedYes


  • Approximation algorithms
  • Data structures
  • Randomized algorithms
  • Range searching
  • Statistical depth

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


Dive into the research topics of 'On approximate range counting and depth'. Together they form a unique fingerprint.

Cite this