Lower bounds for computing statistical depth

Greg Aloupis, Carmen Cortés, Francisco Gómez, Michael Soss, Godfried Toussaint

Research output: Contribution to journalArticlepeer-review


Given a finite set of points S, two measures of the depth of a query point χ with respect to S are the Simplicial depth of Liu and the Halfspace depth of Tukey (also known as Location depth). We show that computing these depths requires Ω(n log n) time, which matches the upper bound complexities of the algorithms of Rousseeuw and Ruts. Our lower bound proofs may also be applied to two bivariate sign tests: that of Hodges, and that of Oja and Nyblom.

Original languageEnglish (US)
Pages (from-to)223-229
Number of pages7
JournalComputational Statistics and Data Analysis
Issue number2
StatePublished - Aug 28 2002


  • Halfspace depth
  • Liu
  • Sign tests
  • Simplical depth
  • Tukey

ASJC Scopus subject areas

  • Statistics and Probability
  • Computational Mathematics
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'Lower bounds for computing statistical depth'. Together they form a unique fingerprint.

Cite this