Simplicial depth

Simplicial depth is robust against outliers: if a set of sample points is represented by the point of maximum depth, then up to a constant fraction of the sample points can be arbitrarily corrupted without significantly changing the location of the representative point. It is also invariant under affine transformations of the plane.^[D][ZS][BRS]

However, simplicial depth fails to have some other desirable properties for robust measures of central tendency. When applied to centrally symmetric distributions, it is not necessarily the case that there is a unique point of maximum depth in the center of the distribution. And, along a ray from the point of maximum depth, it is not necessarily the case that the simplicial depth decreases monotonically.^[ZS][BRS]

For sets of ${\displaystyle n}$ sample points in the Euclidean plane (${\displaystyle d=2}$), the simplicial depth of any other point ${\displaystyle p}$ can be computed in time ${\displaystyle O(n\log n)}$,^{[KM][GSW][RR]} optimal in some models of computation.^[ACG] In three dimensions, the same problem can be solved in time ${\displaystyle O(n^{2})}$.^[CO]

It possible to construct a data structure using ε-nets that can approximate the simplicial depth of a query point (given either a fixed set of samples, or a set of samples undergoing point insertions) in near-constant time per query, in any dimension, with an approximation whose error is a small fraction of the total number of triangles determined by the samples.^[BCE] In two dimensions, a more accurate approximation algorithm is known, for which the approximation error is a small multiple of the simplicial depth itself. The same methods also lead to fast approximation algorithms in higher dimensions.^[ASS]

Spherical depth, ${\displaystyle SphD(q;F)}$ is defined to be the probability that a point ${\displaystyle q}$ is contained inside a random closed hyperball obtained from a pair of points from ${\displaystyle F\subset \mathbb {R} ^{n}}$. While the time complexity of most other data depths grows exponentially, the spherical depth grows only linearly in the dimension ${\displaystyle d}$ – the straightforward algorithm for computing the spherical depth takes ${\displaystyle O(dn^{2})}$. Simplicial depth (SD) is linearly bounded by spherical depth (${\displaystyle SphD\geq {\frac {2}{3}}SD}$).^[BS]