Simplicial depth

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 {{nowrap|contains $p$.}} This probability can be calculated, from the number of simplices that {{nowrap|contain $p$,}} by dividing by $\backslash tbinom\{n\}\{d+1\}$ where $n$ is the number of sample points.{{ran|L88}}{{ran|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, {{harvtxt|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 {{nowrap|contain $p$.{{ran|BRS}}}}

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.{{ran|D}}{{ran|ZS}}{{ran|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.{{ran|ZS}}{{ran|BRS}}

For sets of $n$ sample points in the Euclidean plane {{nowrap|($d=2$),}}

the simplicial depth of any other point $p$ can be computed in time {{nowrap|$O(n\backslash log\; n)$,{{ran|KM}}{{ran|GSW}}{{ran|RR}}}}

optimal in some models of computation.{{ran|ACG}}

In three dimensions, the same problem can be solved in time {{nowrap|$O(n^2)$.{{ran|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.{{ran|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.{{ran|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\; \backslash in\; \backslash 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\; \backslash ge\; \backslash frac\{2\}\{3\}SD$).{{ran|BS}}

{{refbegin|30em}}

{{rma|ASS|{{citation

| last1 = Afshani | first1 = Peyman

| last2 = Sheehy | first2 = Donald R.

| last3 = Stein | first3 = Yannik

| arxiv = 1512.04856

| title = Approximating the simplicial depth

| year = 2015| bibcode = 2015arXiv151204856A}}|tw=3em}}

{{rma|ACG|{{citation

| last1 = Aloupis | first1 = Greg

| last2 = Cortés | first2 = Carmen

| last3 = Gómez | first3 = Francisco

| last4 = Soss | first4 = Michael

| last5 = Toussaint | first5 = Godfried | author5-link = Godfried Toussaint

| doi = 10.1016/S0167-9473(02)00032-4

| issue = 2

| journal = Computational Statistics & Data Analysis

| mr = 1924007

| pages = 223–229

| title = Lower bounds for computing statistical depth

| volume = 40

| year = 2002| s2cid = 94060939

}}|tw=3em}}

{{rma|BCE|{{citation

| last1 = Bagchi | first1 = Amitabha

| last2 = Chaudhary | first2 = Amitabh

| last3 = Eppstein | first3 = David | author3-link = David Eppstein

| last4 = Goodrich | first4 = Michael T. | author4-link = Michael T. Goodrich

| doi = 10.1145/1240233.1240239

| issue = 2

| journal = ACM Transactions on Algorithms

| mr = 2335299

| page = Art. 16, 18

| title = Deterministic sampling and range counting in geometric data streams

| volume = 3

| year = 2007| arxiv = cs/0307027| s2cid = 123315817

}}|tw=3em}}

{{rma|BRS|{{citation

| last1 = Burr | first1 = Michael A.

| last2 = Rafalin | first2 = Eynat

| last3 = Souvaine | first3 = Diane L. | author3-link = Diane Souvaine

| contribution = Simplicial depth: An improved definition, analysis, and efficiency for the finite sample case

| contribution-url = http://www.cccg.ca/proceedings/2004/49.pdf

| pages = 136–139

| title = Proceedings of the 16th Canadian Conference on Computational Geometry, CCCG'04, Concordia University, Montréal, Québec, Canada, August 9-11, 2004

| year = 2004}}|tw=3em}}

{{rma|BS|{{citation

| last1 = Bremner | first1 = David

| last2 = Shahsavarifar | first2 = Rasoul

| arxiv = 1702.07399

| title = An Optimal Algorithm for Computing the Spherical Depth of Points in the Plane

| year = 2017| bibcode = 2017arXiv170207399B}}|tw=3em}}

{{rma|CO|{{citation

| last1 = Cheng | first1 = Andrew Y.

| last2 = Ouyang | first2 = Ming

| contribution = On algorithms for simplicial depth

| contribution-url = http://www.cccg.ca/proceedings/2001/ouyang-24534.ps.gz

| pages = 53–56

| title = Proceedings of the 13th Canadian Conference on Computational Geometry, University of Waterloo, Ontario, Canada, August 13-15, 2001

| year = 2001}}|tw=3em}}

{{rma|D|{{citation

| last = Dümbgen | first = Lutz

| doi = 10.1016/0167-7152(92)90075-G

| issue = 2

| journal = Statistics & Probability Letters

| mr = 1173409

| pages = 119–128

| title = Limit theorems for the simplicial depth

| volume = 14

| year = 1992}}|tw=3em}}

{{rma|GSW|{{citation

| last1 = Gil | first1 = Joseph

| last2 = Steiger | first2 = William

| last3 = Wigderson | first3 = Avi | author3-link = Avi Wigderson

| doi = 10.1016/0012-365X(92)90658-3

| issue = 1–3

| journal = Discrete Mathematics

| mr = 1189827

| pages = 37–51

| title = Geometric medians

| volume = 108

| year = 1992| doi-access = free

}}|tw=3em}}

{{rma|KM|{{citation

| last1 = Khuller | first1 = Samir | author1-link = Samir Khuller

| last2 = Mitchell | first2 = Joseph S. B. | author2-link = Joseph S. B. Mitchell

| doi = 10.1016/0020-0190(90)90217-L

| issue = 6

| journal = Information Processing Letters

| mr = 1045522

| pages = 319–321

| title = On a triangle counting problem

| volume = 33

| year = 1990| doi-access = free

}}|tw=3em}}

{{rma|L88|{{citation

| last = Liu | first = Regina Y. | authorlink = Regina Liu

| doi = 10.1073/pnas.85.6.1732

| issue = 6

| journal = Proceedings of the National Academy of Sciences of the United States of America

| mr = 930658

| pages = 1732–1734

| title = On a notion of simplicial depth

| volume = 85

| year = 1988| bibcode = 1988PNAS...85.1732L| pmc = 279852 | pmid=16578830| doi-access = free }}|tw=3em}}

{{rma|L90|{{citation

| last = Liu | first = Regina Y. | authorlink = Regina Liu

| doi = 10.1214/aos/1176347507

| issue = 1

| journal = Annals of Statistics

| mr = 1041400

| pages = 405–414

| title = On a notion of data depth based on random simplices

| volume = 18

| year = 1990| doi-access = free

}}|tw=3em}}

{{rma|RR|{{citation

| last1 = Rousseeuw | first1 = Peter J. | author1-link = Peter Rousseeuw

| last2 = Ruts | first2 = Ida

| doi = 10.2307/2986073

| issue = 4

| journal = Applied Statistics

| page = 516

| title = Algorithm AS 307: Bivariate Location Depth

| volume = 45

| year = 1996| jstor = 2986073 }}|tw=3em}}

{{rma|ZS|{{citation

| last1 = Zuo | first1 = Yijun

| last2 = Serfling | first2 = Robert

| doi = 10.1214/aos/1016218226

| issue = 2

| journal = Annals of Statistics

| mr = 1790005

| pages = 461–482

| title = General notions of statistical depth function

| volume = 28

| year = 2000| citeseerx = 10.1.1.27.7358

}}|tw=3em}}

{{refend}}

Category:Computational geometry

Category:Robust statistics