David Eppstein - Publications

We generalize regression depth to k-flats. The k=0 case gives the classical notion of center points. We prove that for any set of n points in R^d there always exists a k-flat with depth at least a constant fraction of n. As a consequence, we derive a linear-time (1+epsilon)-approximation algorithm for the deepest flat. The full version of this paper also includes results from "Computing the Depth of a Flat".

(SCG paper)