TY - JOUR
TI - On Algorithms for Simplicial Depth
DO - https://doi.org/doi:10.7282/T3FF3WZ2
AU - Ouyang, Ming
AU - Cheng, Andrew Y.
PY - 2001-08
AB - Simplicial depth is a way to measure how deep a point is among a set of points. Efficient algorithms to compute it are important to the usefulness of its applications, such as in multivariate analysis in statistics. A straightforward method takes O(nd+1) time when the points are in d-dimensional space. We discuss an algorithm that takes O(n2) time when the points are in three-dimensional space, and we generalize it to four-dimensional space with a time complexity of O(n4). For spaces higher than four-dimensional, there are no known algorithms faster than the straightforward method.
LA - English
ER -