Output-sensitive algorithms for Tukey depth and related problems
Output-sensitive algorithms for Tukey depth and related problems
复制标题
Tukey 深度及相关问题的输出敏感算法
作者：
David Bremner;Dan Chen;J. Iacono;S. Langerman;Pat Morin
点p相对于有限点集S的Tukey深度（Proceedings of the International Congress of Mathematicians，第2卷，第523-531页，1975）是包含在包含p的任何闭半空间中的S的元素的最小数目。这些算法的运行时间取决于输出的值，使它们适合于输出值通常很小的情况，例如离群值删除。
The Tukey depth (Proceedings of the International Congress of Mathematicians, vol. 2, pp. 523–531, 1975) of a point p with respect to a finite set S of points is the minimum number of elements of S contained in any closed halfspace that contains p. Algorithms for computing the Tukey depth of a point in various dimensions are considered. The running times of these algorithms depend on the value of the output, making them suited to situations, such as outlier removal, where the value of the output is typically small.