Output-sensitive algorithms for Tukey depth and related problems

David Bremner; Dan Chen; John Iacono; Stefan Langerman; Pat Morin

doi:10.1007/s11222-008-9054-2

Output-sensitive algorithms for Tukey depth and related problems

David Bremner, Dan Chen, John Iacono, Stefan Langerman, Pat Morin

Research output: Contribution to journal › Article › peer-review

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	https://doi.org/10.1007/s11222-008-9054-2
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

Access to Document

10.1007/s11222-008-9054-2

Cite this

@article{afe8f39ddb484407903552318e7698f1,

title = "Output-sensitive algorithms for Tukey depth and related problems",

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.",

keywords = "Algorithms, Computational geometry, Computational statistics, Fixed-parameter tractability, Halfspace depth, Tukey depth",

author = "David Bremner and Dan Chen and John Iacono and Stefan Langerman and Pat Morin",

note = "Funding Information: This research was partly funded by the NSERC Canada.",

year = "2008",

month = sep,

doi = "10.1007/s11222-008-9054-2",

language = "English (US)",

volume = "18",

pages = "259--266",

journal = "Statistics and Computing",

issn = "0960-3174",

publisher = "Springer Netherlands",

number = "3",

}

TY - JOUR

T1 - Output-sensitive algorithms for Tukey depth and related problems

AU - Bremner, David

AU - Chen, Dan

AU - Iacono, John

AU - Langerman, Stefan

AU - Morin, Pat

N1 - Funding Information: This research was partly funded by the NSERC Canada.

PY - 2008/9

Y1 - 2008/9

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

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

KW - Algorithms

KW - Computational geometry

KW - Computational statistics

KW - Fixed-parameter tractability

KW - Halfspace depth

KW - Tukey depth

UR - http://www.scopus.com/inward/record.url?scp=45449089439&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=45449089439&partnerID=8YFLogxK

U2 - 10.1007/s11222-008-9054-2

DO - 10.1007/s11222-008-9054-2

M3 - Article

AN - SCOPUS:45449089439

SN - 0960-3174

VL - 18

SP - 259

EP - 266

JO - Statistics and Computing

JF - Statistics and Computing

IS - 3

ER -

Output-sensitive algorithms for Tukey depth and related problems

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this