On algorithms for simplicial depth
A.Y. Cheng (FAA William J. Hughes Technical Center);
M. Ouyang (EOHSI, UMDNJ - R.W. Johnson Medical School and Rutgers University)
Simplicial depth measures how deep a point is among a set of points. Efficient algorithms to compute it are important to its usefulness in applications, such as multivariate analysis in environmental health and bioinformatics. When the points are in Ed, a straightforward method takes O(nd+1) time. We discuss an algorithm that takes O(n2) time when the points are in E3, and we generalize it to E4 with a time complexity of O(n4).