On algorithms for simplicial depth
Simplicial depth is a way to measure how deep a point is among a set of points. EEcient algorithms to compute it are important to the usefulness of its applications, such as in multivariate analysis in statistics. A straightforward method takes O(n d+1) time when the points are in d-dimensional space. We discuss an algorithm that takes O(n 2) time when the points are in three-dimensional space, and we generalize it to four-dimensional space with a time complexity of O(n 4). For spaces higher than four-dimensional, there are no known algorithms faster than the straightforward method. A simplex in d-dimensional Euclidean space E d is the set of points that are convex combinations of d + 1 aanely independent points; that is, if the points are p 1 ; p 2 ; : : : ; p d+1 , they bring about the simplex fp : p = a 1 p 1 + a 2 p 2 + : : : + a d+1 p d+1 ; a i 0 and X a i = 1g: A simplex is a line segment in E 1 , a triangle in E 2 , and a tetrahedron in E 3. It is customary to say that a set of points in E d are in general position if any d + 1 points in the set are aanely independent. Let P be a set of n points in general position in E d ; take every d + 1 distinct points from P and they uniquely identify a simplex in E d ; let S P be the set of all such simplices; then, jS P j = (n d+1). Let (p; P) denote the simplicial depth of a point p with respect to a set P , deened by (p; P) = jfs 2 S P : p 2 sgj: For example, if p is outside the convex hull of P , then (p; P) = 0, and if p is a vertex of the convex hull of P , then (p; P) = (n?1 d). When p is in P , the following identity holds: