# Exact computation of the halfspace depth

arXiv: https://arxiv.org/abs/1411.6927 · HTML: https://mlsanity.com/paper/1411.6927/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Nov 2014.

## Built on by (most cited first, 11 of 11)

- [Statistical Depth Meets Machine Learning: Kernel Mean Embeddings and Depth in Functional Data Analysis](https://mlsanity.com/paper/2105.12778/) (2021)
- [Statistical Depth Functions for Ranking Distributions: Definitions, Statistical Learning and Applications](https://mlsanity.com/paper/2201.08105/) (2022)
- [Anomaly detection using data depth: multivariate case](https://mlsanity.com/paper/2210.02851/) (2022)
- [Tukey Depths and Hamilton-Jacobi Differential Equations](https://mlsanity.com/paper/2104.01648/) (2021)
- [Beyond Mahalanobis-Based Scores for Textual OOD Detection](https://mlsanity.com/paper/2211.13527/) (2022)
- [Differentially private multivariate medians](https://mlsanity.com/paper/2210.06459/) (2022)
- [On the quality of randomized approximations of Tukey's depth](https://mlsanity.com/paper/2309.05657/) (2023)
- [Tukey Depth Mechanisms for Practical Private Mean Estimation](https://mlsanity.com/paper/2502.18698/) (2025)
- [Feature Selection using e-values](https://mlsanity.com/paper/2206.05391/) (2022)
- [seMCD: Sequentially implemented Monte Carlo depth computation with statistical guarantees](https://mlsanity.com/paper/2507.06227/) (2025)
- [A Trainable Centrality Framework for Modern Data](https://mlsanity.com/paper/2511.22959/) (2025)

## Abstract (arXiv)

For computing the exact value of the halfspace depth of a point w.r.t. a data cloud of n points in arbitrary dimension, a theoretical framework is suggested. Based on this framework a whole class of algorithms can be derived. In all of these algorithms the depth is calculated as the minimum over a finite number of depth values w.r.t. proper projections of the data cloud. Three variants of this class are studied in more detail. All of these algorithms are capable of dealing with data that are not in general position and even with data that contain ties. As is shown by simulations, all proposed algorithms prove to be very efficient.