## 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 R^{d} 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.)