Paper Info
Title
Fast implementation of depth contours using topological sweep
Abstract
The concept of location depth was introduced in statistics 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. These require the computation of depth regions, which form a collection of nested polygons. The center of the deepest region 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 depth contours in &Ogr;(n2) time and space, using topological sweep of the dual arrangement of lines. Once the contours are known, the location depth of any point is computed in &Ogr;(log2 n) time. We provide fast implementations of these algorithms to allow their use in everyday statistical practice.
Year
DOI
Venue
2001
10.5555/365411.365565
SODA
Keywords
Field
DocType
everyday statistical practice,tukey median,fast implementation,data point,bivariate configuration,depth region,dual arrangement,deepest region,topological sweep,location depth,depth contour,dominating set,edge coloring,clique width,hypothesis test,robust estimator
Data point,Discrete mathematics,Topology,Polygon,Combinatorics,Ranking,Computer science,Arrangement of lines,Edge dominating set,Univariate,Statistical hypothesis testing,Computation
Conference
ISBN
Citations 
PageRank 
0-89871-490-7
14
2.09
References 
Authors
5
7
Name
Order
Citations
PageRank
Kim Miller1303.07
Suneeta Ramaswami222823.87
Peter Rousseeuw3637.23
Toni Sellarès4142.42
Diane L. Souvaine548077.99
Ileana Streinu651064.64
Anja Struyf78511.63