Output-sensitive algorithms for Tukey depth and related problems |
| |
| Authors: | David Bremner Dan Chen John Iacono Stefan Langerman Pat Morin |
| |
| Affiliation: | (1) University of New Brunswick, New Brunswick, Canada;(2) Carleton University, Ottawa, Ontario, Canada;(3) Polytechnic University, Brooklyn, NY, USA;(4) Université Libre de Bruxelles, Brussels, Belgium;(5) School of Computer Science, Carleton University, 1125 Colonel By Drive, Ottawa, Ontario, K1S 5B6, Canada |
| |
| Abstract: | 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. This research was partly funded by the NSERC Canada. |
| |
| Keywords: | Tukey depth Halfspace depth Algorithms Computational statistics Computational geometry Fixed-parameter tractability |
| 本文献已被 SpringerLink 等数据库收录！ |
|
