Simplicial depth

In robust statistics and computational geometry, simplicial depth is a measure of central tendency determined by the simplices that contain a given point.

-dimensional simplices (the convex hulls of sets of

The same notion can be generalized to any probability distribution on points of the plane, not just the empirical distribution given by a set of sample points, by defining the depth to be the probability that a randomly chosen

-tuple of points has a convex hull that contains

This probability can be calculated, from the number of simplices that contain

[L88][L90] Under the standard definition of simplicial depth, the simplices that have

on their boundaries count equally much as the simplices with

In order to avoid some problematic behavior of this definition, Burr, Rafalin & Souvaine (2004) proposed a modified definition of simplicial depth, in which the simplices with

Equivalently, their definition is the average of the number of open simplices and the number of closed simplices that contain

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.

[ACG] In three dimensions, the same problem can be solved in time

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.

is contained inside a random closed hyperball obtained from a pair of points from

While the time complexity of most other data depths grows exponentially, the spherical depth grows only linearly in the dimension

– the straightforward algorithm for computing the spherical depth takes