**Multivariate regression depth**.

M. Bern and D. Eppstein.

arXiv:cs.CG/9912013.

*16th ACM Symp. Comp. Geom.,*Hong Kong, 2000, pp. 315–321.

*Disc. Comp. Geom.*28 (1): 1–17, 2002.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".

Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine

Semi-automatically filtered from a common source file.