Title: Efficient computation of location depth contours by methods of computational geometry
Authors: Rousseeuw, Peter ×
Miller, Kim
Ramaswami, Suneeta
Sellarès, Antoni
Streinu, Ileana
Struyf, Anja #
Issue Date: 2003
Publisher: Kluwer Academic Publishers
Series Title: Statistics and Computing vol:13 issue:2 pages:153-162
Abstract: The concept of location depth was introduced as a way to extend the univariate notion of ranking to a bivariate configuration of data points. It has been used successfully for robust estimation, hypothesis testing, and graphical display. The depth contours form a collection of nested polygons, and the center of the deepest contour is called the Tukey median. The only available implemented algorithms for the depth contours and the Tukey median are slow, which limits their usefulness. In this paper we describe an optimal algorithm which computes all bivariate depth contours in O(n 2) time and space, using topological sweep of the dual arrangement of lines. Once these contours are known, the location depth of any point can be computed in O(log2 n) time with no additional preprocessing or in O(log n) time after O(n 2) preprocessing. We provide fast implementations of these algorithms to allow their use in everyday statistical practice.
ISSN: 0960-3174
Publication status: published
KU Leuven publication type: IT
Appears in Collections:Statistics Section
× corresponding author
# (joint) last author

Files in This Item:

There are no files associated with this item.

Request a copy


All items in Lirias are protected by copyright, with all rights reserved.

© Web of science