language: en

On Algorithms for Simplicial Depth

Andrew Y. Cheng
Department of Industrial Engineering
Ming Ouyang
Department of Computer Science Rutgers University
New Brunswick, New Jersey 08903

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(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.

1 Simplicial depth