# Approximating the Simplicial Depth

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Dec 2015.

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

- [Differentially private multivariate medians](https://mlsanity.com/paper/2210.06459/) (2022)
- [Adaptive Data Depth via Multi-Armed Bandits](https://mlsanity.com/paper/2211.03985/) (2022)

## Abstract (arXiv)

Let P be a set of n points in d-dimensions. The simplicial depth, σP(q) of a point q is the number of d-simplices with vertices in P that contain q in their convex hulls. The simplicial depth is a notion of data depth with many applications in robust statistics and computational geometry. Computing the simplicial depth of a point is known to be a challenging problem. The trivial solution requires O(nd+1) time whereas it is generally believed that one cannot do better than O(nd-1). In this paper, we consider approximation algorithms for computing the simplicial depth of a point. For d=2, we present a new data structure that can approximate the simplicial depth in polylogarithmic time, using polylogarithmic query time. In 3D, we can approximate the simplicial depth of a given point in near-linear time, which is clearly optimal up to polylogarithmic factors. For higher dimensions, we consider two approximation algorithms with different worst-case scenarios. By combining these approaches, we compute a (1+varepsilon)-approximation of the simplicial depth in time tildeO(nd/2 + 1) ignoring polylogarithmic factor. All of these algorithms are Monte Carlo algorithms. Furthermore, we present a simple strategy to compute the simplicial depth exactly in O(nd log n) time, which provides the first improvement over the trivial O(nd+1) time algorithm for d>4. Finally, we show that computing the simplicial depth exactly is #P-complete and W[1]-hard if the dimension is part of the input.