Statistical depth meets computational geometry: a short survey <s> Bivariate algorithms <s> The notion of a centerpoint of a finite set of points in two and higher dimensions is a generalisation of the concept of the median of a (finite) set of points on the real line. In this paper, we present an algorithm for computing a centerpoint of a set of <italic>n</italic> points in the plane. The algorithm has complexity <italic>O(n)</italic> which significantly improves the <italic>O(n log<supscrpt>3</supscrpt> n)</italic> complexity of the previously best known algorithm. We use suitable modifications of the ham-sandwich-cut algorithm and the prune-and-search technique to achieve this improvement. <s> BIB001 </s> Statistical depth meets computational geometry: a short survey <s> Bivariate algorithms <s> Abstract In this paper we construct an exact algorithm for computing depth contours of a bivariate data set. For this we use the half-space depth introduced by Tukey. The depth contours form a nested collection of convex sets. The deeper the contour, the more robust it is with respect to outliers in the point cloud. The proposed algorithm has been implemented in a program called ISODEPTH, which needs little computation time and is illustrated on some real data examples. Finally, it is shown how depth contours can be used to construct robustified versions of classification techniques based on convex hulls. <s> BIB002 </s> Statistical depth meets computational geometry: a short survey <s> Bivariate algorithms <s> Given a set of n hyperplanes h1,ź,hn \in Rd the hyperplane depth of a point P\in Rd is the minimum number of hyperplanes that a ray from P can meet. The hyperplane depth of the arrangement is the maximal depth of points P not in any hi. We give an optimal O(nlogn) deterministic algorithm to compute the hyperplane depth of an arrangement in dimension d = 2. <s> BIB003 </s> Statistical depth meets computational geometry: a short survey <s> Bivariate algorithms <s> Many problems can be formulated as the optimization of functions in R 2 which are implicitly defined by an arrangement of lines, halfplanes, or points, for example linear programming in the plane. We present an efficient general approach to find the optimum exactly, for a wide range of functions that possess certain useful properties. To illustrate the value of this approach, we give a variety of applications in which we speed up or simplify the best known algorithms. These include algorithms for finding robust geometric medians (such as the Tukey Median), robust regression lines, and ham-sandwich cuts. © Springer-Verlag Berlin Heidelberg 2003. <s> BIB004 </s> Statistical depth meets computational geometry: a short survey <s> Bivariate algorithms <s> Half-space depth (also called Tukey depth or location depth) is one of the most commonly studied data depth measures because it possesses many desirable properties for data depth functions. The data depth contours bound regions of increasing depth. For the sample case, there are two competing definitions of contours: the rank-based contours and the cover-based contours. In this paper, we present three dynamic algorithms for maintaining the half-space depth of points and contours: The first maintains the half-space depth of a single point in a data set in $O(\log n)$ time per update (insertion/deletion) and overall linear space. By maintaining such a data structure for each data point, we present an algorithm for dynamically maintaining the rank-based contours in $O(n\cdot\log n)$ time per update and overall quadratic space. The third dynamic algorithm maintains the cover-based contours in $O(n\cdot \log^2 n)$ time per update and overall quadratic space. We also augment our first algorithm to maintain the local cover-based contours at data points while maintaining the same complexities. A corollary of this discussion is a strong structural result of independent interest describing the behavior of dynamic cover-based contours near data points. <s> BIB005
In general, computing a median is harder than computing the depth in a point, because typically there are many candidate points. For instance, for the bivariate simplicial median the currently best algorithm requires O(n 4 ) time, whereas its corresponding depth needs only O(n log n). The simplicial median seems difficult to compute because there are O(n 4 ) candidate points (namely, all intersections of lines passing through two data points) and the simplicial depth regions have irregular shapes, but of course a faster algorithm may yet be found. Fortunately, in several important cases the median can be computed without computing the depth of individual points. A linear-time algorithm to compute a bivariate centerpoint was described in BIB001 . Table 3 gives an overview of algorithms to compute bivariate depth-based medians. For the bivariate Tukey median the lower bound Ω(n log n) was proved in  , and the currently fastest algorithm takes O(n log 3 n) time ( BIB004 ). The lower bound Ω(n log n) also holds for the median of arrangement (regression) depth as shown by BIB003 . Fast algorithms were devised by BIB003 and [VMR + 08]. The computation of bivariate halfspace depth regions has also been studied. The first algorithm BIB002 required O(n 2 log n) time per depth region. An algorithm to compute all regions in O(n 2 ) time is constructed and implemented in [MRR + 03] . This algorithm thus also yields the Tukey median. It is based on the dual arrangement of lines where topological sweep is applied. A completely different approach is implemented in  . They make direct use of the graphics hardware to approximate the depth regions of a set of points in O(nW + W 3 ) + nCW 2 /512 time, where the pixel grid is of dimension (2W + 1) × (2W + 1). Recently, BIB005 constructed an algorithm to update halfspace depth and its regions when points are added to the data set.