Statistical depth meets computational geometry: a short survey <s> Algorithms in higher dimensions <s> A set of n distinct points in the plane defines lines by joining each pair of distinct points. The median slope of these O(n2) lines was proposed by Theil as a robust estimator for the slope of the line of best fit for the points. We present a randomized algorithm for selecting the k-th smallest slope of such a set of lines which runs in expected O(n log n) time. An efficient implementation of the algorithm and practical experience with the algorithm are discussed. <s> BIB001 </s> Statistical depth meets computational geometry: a short survey <s> Algorithms in higher dimensions <s> The location depth (Tukey 1975) of a point θ relative to a p-dimensional data set Z of size n is defined as the smallest number of data points in a closed halfspace with boundary through θ. For bivariate data, it can be computed in O(nlogn) time (Rousseeuw and Ruts 1996). In this paper we construct an exact algorithm to compute the location depth in three dimensions in O(n2logn) time. We also give an approximate algorithm to compute the location depth in p dimensions in O(mp3+mpn) time, where m is the number of p-subsets used. ::: ::: Recently, Rousseeuw and Hubert (1996) defined the depth of a regression fit. The depth of a hyperplane with coefficients (θ1,…,θp) is the smallest number of residuals that need to change sign to make (θ1,…,θp) a nonfit. For bivariate data (p=2) this depth can be computed in O(nlogn) time as well. We construct an algorithm to compute the regression depth of a plane relative to a three-dimensional data set in O(n2logn) time, and another that deals with p=4 in O(n3logn) time. For data sets with large n and/or p we propose an approximate algorithm that computes the depth of a regression fit in O(mp3+mpn+mnlogn) time. For all of these algorithms, actual implementations are made available. <s> BIB002 </s> Statistical depth meets computational geometry: a short survey <s> Algorithms in higher dimensions <s> Abstract We give an optimal deterministic O(n log n)-time algorithm for slope selection. The algorithm borrows from the optimal solution given in (Cole et al., 1989) but avoids the complicated machinery of the AKS sorting network and parametric searching. This is achieved by redesigning and refining the O(n log2 n)-time algorithm of Chazelle et al. (1993) with the help of additional approximation tools. <s> BIB003 </s> Statistical depth meets computational geometry: a short survey <s> Algorithms in higher dimensions <s> The halfspace location depth of a point relative to a data set Xn is dened as the smallest number of observations in any closed halfspace with boundary through . As such, halfspace depth can be seen as a kind of multivariate ranking. The deepest location, i.e. the with maximal halfspace depth, is a multivariate generalization of the median. Until now the deepest location could only be computed for bivariate data. In this paper, we construct an algorithm (called DEEPLOC) to approximate the deepest location in higher dimensions. c 2000 Elsevier Science B.V. All rights reserved. <s> BIB004 </s> Statistical depth meets computational geometry: a short survey <s> Algorithms in higher dimensions <s> 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. <s> BIB005 </s> Statistical depth meets computational geometry: a short survey <s> Algorithms in higher dimensions <s> The use of quantiles to obtain insights about multivariate data is ad- dressed. It is argued that incisive insights can be obtained by considering direc- tional quantiles, the quantiles of projections. Directional quantile envelopes are proposed as a way to condense this kind of information; it is demonstrated that they are essentially halfspace (Tukey) depth levels sets, coinciding for elliptic distri- butions (in particular multivariate normal) with density contours. Relevant ques- tions concerning their indexing, the possibility of the reverse retrieval of directional quantile information, invariance with respect to affine transformations, and approx- imation/asymptotic properties are studied. It is argued that analysis in terms of directional quantiles and their envelopes offers a straightforward probabilistic inter- pretation and thus conveys a concrete quantitative meaning; the directional defini- tion can be adapted to elaborate frameworks, like estimation of extreme quantiles and directional quantile regression, the regression of depth contours on covariates. The latter facilitates the construction of multivariate growth charts—the question that motivated this development. <s> BIB006 </s> Statistical depth meets computational geometry: a short survey <s> Algorithms in higher dimensions <s> A new multivariate concept of quantile, based on a directional version of Koenker and Bassett’s traditional regression quantiles, is introduced for multivariate location and multiple-output regression problems. In their empirical version, those quantiles can be computed efficiently via linear programming techniques. Consistency, Bahadur representation and asymptotic normality results are established. Most importantly, the contours generated by those quantiles are shown to coincide with the classical halfspace depth contours associated with the name of Tukey. This relation does not only allow for efficient depth contour computations by means of parametric linear programming, but also for transferring from the quantile to the depth universe such asymptotic results as Bahadur representations. Finally, linear programming duality opens the way to promising developments in depth-related multivariate rank-based inference. (This abstract was borrowed from another version of this item.) <s> BIB007 </s> Statistical depth meets computational geometry: a short survey <s> Algorithms in higher dimensions <s> A Monte Carlo approximation algorithm for the Tukey depth problem in high dimensions is introduced. The algorithm is a generalization of an algorithm presented by Rousseeuw and Struyf (1998) [20]. The performance of this algorithm is studied both analytically and experimentally. <s> BIB008 </s> Statistical depth meets computational geometry: a short survey <s> Algorithms in higher dimensions <s> For computing the exact value of the halfspace depth of a point w.r.t. a data cloud of $n$ points in arbitrary dimension, a theoretical framework is suggested. Based on this framework a whole class of algorithms can be derived. In all of these algorithms the depth is calculated as the minimum over a finite number of depth values w.r.t. proper projections of the data cloud. Three variants of this class are studied in more detail. All of these algorithms are capable of dealing with data that are not in general position and even with data that contain ties. As is shown by simulations, all proposed algorithms prove to be very efficient. <s> BIB009 </s> Statistical depth meets computational geometry: a short survey <s> Algorithms in higher dimensions <s> Given data in $\mathbb{R}^{p}$, a Tukey $\tau$-trimmed region is the set of all points that have at least Tukey depth $\tau$ in the data. As they are visual, affine equivariant and robust, Tukey trimmed regions are useful tools in nonparametric multivariate analysis. While these regions are easily defined and can be interpreted as $p$-variate quantiles, their practical application is impeded by the lack of efficient computational procedures in dimension $p>2$. We construct two algorithms that exploit certain combinatorial properties of the regions. Both calculate the exact region. They run much faster and require substantially less RAM than existing ones. <s> BIB010 </s> Statistical depth meets computational geometry: a short survey <s> Algorithms in higher dimensions <s> To facilitate the application of projection depth, an exact algorithm is proposed from the view of cutting a convex polytope with hyperplanes. Based on this algorithm, one can obtain a finite number of optimal direction vectors, which are x-free and therefore enable us (Liu et al., Preprint, 2011) to compute the projection depth and most of its associated estimators of dimension p?2, including Stahel-Donoho location and scatter estimators, projection trimmed mean, projection depth contours and median, etc. Both real and simulated examples are also provided to illustrate the performance of the proposed algorithm. <s> BIB011
The first algorithms to compute the halfspace and regression depth of a given point in R d with d > 2 were constructed in BIB002 and require O(n d−1 log n) time. The main idea was to use projections onto a lower-dimensional space. This reduces the problem to computing bivariate depths, for which the existing algorithms have optimal time complexity. In BIB005 theoretical output-sensitive algorithms for the halfspace depth are proposed. An interesting computational connection between halfspace depth and multivariate quantiles was provided in BIB007 and BIB006 . More recently, BIB009 provided a generalized version of the algorithm of BIB002 together with C++ code. For the depth regions of halfspace depth in higher dimensions an algorithm was recently proposed in BIB010 . For the computation of projection depth see BIB011 . The simplicial depth of a point in R 3 can be computed in O(n 2 ) time, and in R 4 the fastest algorithm needs O(n 4 ) time  . For higher dimensions, no better algorithm is known than the straightforward O(n d+1 ) method to compute all simplices. When the number of data points and dimensions are such that the above algorithms become infeasible, one can resort to approximate algorithms. For halfspace depth such approximate algorithms were proposed in BIB002 and BIB008 . An approximation to the Tukey median using steepest descent can be found in BIB004 . In [VRH + 02] an algorithm is described to approximate the deepest regression fit in any dimension. 3 Some other statistical techniques benefitting from computational geometry Computational geometry has provided fast and reliable algorithms for many other statistical techniques. Linear regression is a frequently used statistical technique. The ordinary least squares regression, minimizing the sum of squares of the residuals, is easy to calculate, but produces unreliable results whenever one or more outliers are present in the data. Robust alternatives are often computationally intensive. We here give some examples of regression methods for which geometric or combinatorial algorithms have been constructed.  ). This bivariate regression technique estimates the slope as the median of the slopes of all lines through two data points. An algorithm with optimal complexity O(n log n) is given in BIB003 , and a more practical randomized algorithm in BIB001 .