David Eppstein - Publications

• 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".

  (SCG paper)

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

Semi-automatically filtered from a common source file.