Computing location depth and regression depth in higher dimensions

The location depth (Tukey 1975) of a point theta 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 theta. For bivariate data? it can be computed in O(n log n) time (Rousseeuw and Ruts 1996). In this paper we construct an exact algorithm to compute the location depth in three dimensions in O(n(2)log n) time. We also give an approximate algorithm to compute the location depth inp dimensions in O(mp(3) + 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 (theta(1),...,theta(p)) is the smallest number of residuals that need to change sign to make (theta(1),...,theta(p)) a nonfit. For bivariate data (p = 2) this depth can be computed in O(n log n) time as well. We construct an algorithm to compute the regression depth of a plane relative to a three-dimensional data set in O(n(2)log n) time, and another that deals with p = 4 in O(n(3) log n) 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(mp(3) + mpn + mn log n) time. For all of these algorithms, actual implementations are made available.