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. For the Euclidean plane, it counts the number of triangles of sample points that contain a given point.

Definition

The simplicial depth of a point $p$ in $d$ -dimensional Euclidean space, with respect to a set of sample points in that space, is the number of $d$ -dimensional simplices (the convex hulls of sets of $d+1$ sample points) that contain $p$ . 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 $(d+1)$ -tuple of points has a convex hull that contains $p$ . This probability can be calculated, from the number of simplices that contain $p$ , by dividing by ${\tbinom {n}{d+1}}$ where $n$ is the number of sample points.^[L88]^[L90]

Under the standard definition of simplicial depth, the simplices that have $p$ on their boundaries count equally much as the simplices with $p$ in their interiors. 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 $p$ on their boundaries count only half as much. Equivalently, their definition is the average of the number of open simplices and the number of closed simplices that contain $p$ .^[BRS]

Properties

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]

Algorithms

For sets of $n$ sample points in the Euclidean plane ( $d=2$ ), the simplicial depth of any other point $p$ can be computed in time $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 $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, $SphD(q;F)$ is defined to be the probability that a point $q$ is contained inside a random closed hyperball obtained from a pair of points from $F\in \mathbb {R} ^{n}$ . While the time complexity of most other data depths grows exponentially, the spherical depth grows only linearly in the dimension $d$ – the straightforward algorithm for computing the spherical depth takes $O(dn^{2})$ . Simplicial depth (SD) is linearly bounded by spherical depth ( $SphD\geq {\frac {2}{3}}SD$ ).^[BS]

References

ASS.

Afshani, Peyman; Sheehy, Donald R.; Stein, Yannik (2015), Approximating the simplicial depth, arXiv:1512.04856, Bibcode:2015arXiv151204856A

ACG.

Aloupis, Greg; Cortés, Carmen; Gómez, Francisco; Soss, Michael; Toussaint, Godfried (2002), "Lower bounds for computing statistical depth", Computational Statistics & Data Analysis, 40 (2): 223–229, doi:10.1016/S0167-9473(02)00032-4, MR 1924007, S2CID 94060939

BCE.

Bagchi, Amitabha; Chaudhary, Amitabh; Eppstein, David; Goodrich, Michael T. (2007), "Deterministic sampling and range counting in geometric data streams", ACM Transactions on Algorithms, 3 (2): Art. 16, 18, arXiv:cs/0307027, doi:10.1145/1240233.1240239, MR 2335299, S2CID 123315817

BRS.

Burr, Michael A.; Rafalin, Eynat; Souvaine, Diane L. (2004), "Simplicial depth: An improved definition, analysis, and efficiency for the finite sample case" (PDF), Proceedings of the 16th Canadian Conference on Computational Geometry, CCCG'04, Concordia University, Montréal, Québec, Canada, August 9-11, 2004, pp. 136–139

BS.

Bremner, David; Shahsavarifar, Rasoul (2017), An Optimal Algorithm for Computing the Spherical Depth of Points in the Plane, arXiv:1702.07399, Bibcode:2017arXiv170207399B

CO.

Cheng, Andrew Y.; Ouyang, Ming (2001), "On algorithms for simplicial depth", Proceedings of the 13th Canadian Conference on Computational Geometry, University of Waterloo, Ontario, Canada, August 13-15, 2001, pp. 53–56

D.

Dümbgen, Lutz (1992), "Limit theorems for the simplicial depth", Statistics & Probability Letters, 14 (2): 119–128, doi:10.1016/0167-7152(92)90075-G, MR 1173409

GSW.

Gil, Joseph; Steiger, William; Wigderson, Avi (1992), "Geometric medians", Discrete Mathematics, 108 (1–3): 37–51, doi:10.1016/0012-365X(92)90658-3, MR 1189827

KM.

Khuller, Samir; Mitchell, Joseph S. B. (1990), "On a triangle counting problem", Information Processing Letters, 33 (6): 319–321, doi:10.1016/0020-0190(90)90217-L, MR 1045522

L88.

Liu, Regina Y. (1988), "On a notion of simplicial depth", Proceedings of the National Academy of Sciences of the United States of America, 85 (6): 1732–1734, Bibcode:1988PNAS...85.1732L, doi:10.1073/pnas.85.6.1732, MR 0930658, PMC 279852, PMID 16578830

L90.

Liu, Regina Y. (1990), "On a notion of data depth based on random simplices", Annals of Statistics, 18 (1): 405–414, doi:10.1214/aos/1176347507, MR 1041400

RR.

Rousseeuw, Peter J.; Ruts, Ida (1996), "Algorithm AS 307: Bivariate Location Depth", Applied Statistics, 45 (4): 516, doi:10.2307/2986073, JSTOR 2986073

ZS.

Zuo, Yijun; Serfling, Robert (2000), "General notions of statistical depth function", Annals of Statistics, 28 (2): 461–482, CiteSeerX 10.1.1.27.7358, doi:10.1214/aos/1016218226, MR 1790005