On computing geometric estimators of location
Greg Aloupis · eScholarship@McGill (McGill) · 2001
Let S be a data set of n points in Rd, and m&d4; be a point in Rd which "best" describes S. Since the term "best" is subjective, there exist several definitions for finding m&d4; . However, it is generally agreed that such a definition, or estimator of location, should have certain statistical properties which make it robust. Most estimators of location assign a depth value to any point in Rd and define m&d4; to be a point with maximum depth. Here, new results are presented concerning the computational complexity of estimators of location. We prove that in R2 the computation of simplicial and halfspace depth of a point requires O (n log n) time, which matches the upper bound complexities of algorithms by Rousseeuw and Ruts. Our lower bounds also apply to two sign tests, that of Hodges and that of Oja and Nyblom. In addition, we propose algorithms which reduce the time complexity of calculating the points with greatest Oja and simplicial depth. Our fastest algorithms use O(n3 log n) and O(n4) time respectively, compared to the algorithms of Rousseeuw and Ruts which use O(n5 log n) time. One of our algorithms may also be used to find a point with minimum weighted sum of distances to a set of n lines in O( n2) time. This point is called the Fermat-Torricelli point of n lines by Roy Barbara, whose algorithm uses O( n3) time. Finally, we propose a new estimator which arises from the notion of hyperplane depth recently defined by Rousseeuw and Hubert.