
Title  Regression Depth and Center Points
(Article) 
in  Discrete and Computational Geometry 
Author(s) 
Nina Amenta, Marshall Bern, David Eppstein, ShangHua Teng 
Year 
2000

Volume  23 
Number  3 
Pages  305323 
Download  
BibTeX  
Abstract 
We show that, for any set of n points in d dimensions, there exists a hyperplane with regression depth at least
[n/(d+1)], as had been conjectured by Rousseeuw and Hubert. Dually, for any arrangement of n hyperplanes in d
dimensions there exists a point that cannot escape to infinity without crossing at least [n/(d+1)]hyperplanes. We also apply our approach to related questions on the existence of partitions of the data into subsets such that a common plane has nonzero regression depth in each subset, and to the computational complexity of regression depth problems.
