Statistical depth meets computational geometry: a short survey <s> Arrangement and regression depth <s> For a general definition of depth in data analysis a differential-like calculus is constructed in which the location case (the framework of Tukey's median) plays a fundamental role similar to that of linear functions in the mathematical analysis. As an application, a lower bound for maximal regression depth is proved in the general multidimensional case-as conjectured by Rousseeuw and Hubert and others. This lower bound is demonstrated to have an impact on the breakdown point of the maximum depth estimator. <s> BIB001 </s> Statistical depth meets computational geometry: a short survey <s> Arrangement and regression depth <s> A collection of n hyperplanes in \({\Bbb R}\) d forms a hyperplane arrangement. The depth of a point \(\theta \in {\Bbb R}^d\) is the smallest number of hyperplanes crossed by any ray emanating from θ . For d=2 we prove that there always exists a point θ with depth at least \(\lceil n/3\rceil\) . For higher dimensions we conjecture that the maximal depth is at least \(\lceil n/(d+1)\rceil\) . For arrangements in general position, an upper bound on the maximal depth is also established. Finally, we discuss algorithms to compute points with maximal depth. <s> BIB002 </s> Statistical depth meets computational geometry: a short survey <s> Arrangement and regression depth <s> ℝ In this paper we first explore the analogies between location depth and regression depth. The location depth of [Tukey (1975)] is a multivariate generalization of rank, and leads to a multivariate median known as the Tukey median or the deepest location. Regression depth was introduced in [Rousseeuw and Hubert (1999b)], and yields the deepest regression which is a new robust regression estimator. Based on the recent literature on depth, we compare several theoretical and computational aspects of depth and of the deepest fits in location and regression. <s> BIB003
Following BIB002 we now define the depth of a point relative to an arrangement of hyperplanes. A point θ is said to have zero arrangement depth if there exists a ray {θ + λu; λ 0} that does not cross any of the hyperplanes h i in the arrangement. (A hyperplane parallel to the ray is counted as intersecting at infinity.) The arrangement depth of any point θ is defined as the minimum number of hyperplanes intersected by any ray from θ. Figure 3 shows an arrangement of lines. In this plot, the points θ and η have arrangement depth 0 and the point ξ has arrangement depth 2. The arrangement depth is always constant on open cells and on cell edges. It was shown ( BIB002 ) that any arrangement of lines in the plane encloses a point with arrangement depth at least ⌈n/3⌉, giving rise to a new type of "centerpoints." This notion of depth was originally defined (  ) in the dual, as the depth of a regression hyperplane H θ relative to a point configuration of the form Z n = {(x 1 , y 1 ), . . . , (x n , y n )} in R d+1 . Regression depth ranks hyperplanes according to how well they fit the data in a regression model, with x containing the predictor variables and y the response. A vertical hyperplane (given by a τ x = constant), which cannot be used to predict future response values, is called a "nonfit" and assigned regression depth 0. The regression depth of a general hyperplane H θ is found by rotating H θ in a continuous movement until it becomes vertical. The minimum number of data points that is passed in such a rotation is called the regression depth of H θ . Figure 4 is the dual representation of Figure 3 . (For instance, the line θ has slope θ 1 and intercept θ 2 and corresponds to the point (θ 1 , θ 2 ) in Figure 3 .) The lines θ and η have regression depth 0, whereas the line ξ has regression depth 2. In statistics one is interested in the deepest fit or regression depth median, because this is a line (hyperplane) about which the data are well-balanced. The statistical properties of regression depth and the deepest fit are very similar to those of the Tukey depth and median. The bounds on the maximal depth are almost the same. Moreover, for both depth notions the value of the maximal depth can be used to characterize the symmetry of the distribution ([RS04]). The breakdown value of the deepest fit is at least 1/(d + 1) and under linearity of the conditional median of y given x it converges to 1/3. In the next section, we will see that the optimal complexities for computing the depth and the median are also comparable to those for halfspace depth. For a detailed comparison of the properties of halfspace and regression depth, see BIB003 . The arrangement depth region D k is defined in the primal, as the set of points with arrangement depth at least k. Contrary to the Tukey depth, these depth regions need not be convex. But nevertheless it was proved that there always exists a point with arrangement depth at least ⌈n/(d+1)⌉ ([ABE + 00]). An analysis-based proof was given in BIB001 . Remark: arrangement levels. Arrangement depth is undirected (isotropic) in the sense that it is defined as a minimum over all possible directions. If we restrict ourselves to vertical directions u (i.e., up or down), we obtain the usual levels of the arrangement known in combinatorial geometry. The absence of preferential directions makes arrangement depth invariant under affine transformations. 