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

Original language | English (US) |
---|---|

Pages (from-to) | 259-266 |

Number of pages | 8 |

Journal | Statistics and Computing |

Volume | 18 |

Issue number | 3 |

DOIs | |

State | Published - Sep 2008 |

### Keywords

- Algorithms
- Computational geometry
- Computational statistics
- Fixed-parameter tractability
- Halfspace depth
- Tukey depth

### ASJC Scopus subject areas

- Theoretical Computer Science
- Statistics and Probability
- Statistics, Probability and Uncertainty
- Computational Theory and Mathematics

## Fingerprint Dive into the research topics of 'Output-sensitive algorithms for Tukey depth and related problems'. Together they form a unique fingerprint.

## Cite this

Bremner, D., Chen, D., Iacono, J., Langerman, S., & Morin, P. (2008). Output-sensitive algorithms for Tukey depth and related problems.

*Statistics and Computing*,*18*(3), 259-266. https://doi.org/10.1007/s11222-008-9054-2