On Algorithms for Simplicial Depth, Proceedsing of the 14th Canadian Conference on Computational Geometry
| Full Text: |
 Pdf
(0.12 MB) |
|
Publication Date: |
01-2001 |
| Authors: |
Andrew Cheng, PhD. Ouyang, M. |
Cheng, A.Y. & Ouyang, M. (2001) On Algorithms for Simplicial Depth, Proceedings of the 13th Canadian Conference on Computational Geometry, pp. 53-56.
Abstract
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.
