Efficient algorithms for maximum regression depth

We investigate algorithmic questions that arise in the statistical problem of computing lines or hyperplanes of maximum regression depth among a set of n points. We work primarily with a dual representation and find points of maximum undirected depth in an arrangement of lines or hyperplanes. An O(n(d)) time and O(n(d-1)) space algorithm computes undirected depth of all points in d dimensions. Properties of undirected depth lead to an O(n log(2) n) time and O(n) space algorithm for computing a point of maximum depth in two dimensions, which has been improved to an O(n log(2) n) time algorithm by Langerman and Steiger (Discrete Comput. Geom. 30(2): 299-309, 2003). Furthermore, we describe the structure of depth in the plane and higher dimensions, leading to various other geometric and algorithmic results.status: publishe