ICS Theory Group

ICS 269, Winter 2000: Theory Seminar


4 February 2000:
Multivariate Regression Depth
David Eppstein, ICS, UC Irvine

The regression depth of a hyperplane with respect to a set of n points in Rd is the minimum number of points the hyperplane must pass through in a rotation to vertical. We generalize hyperplane regression depth to k-flats for any k between 0 and d-1. The k=0 case gives the classical notion of center points. We prove that for any k and d, deep k-flats exist, that is, for any set of n points 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.

(To appear at SCG'00; full paper available in ACM Computing Research Repository, cs.CG/9912013.)