Regression depth and center points.
N. Amenta,
M. Bern,
D. Eppstein, and
S.-H. Teng.
arXiv:cs.CG/9809037.
3rd CGC
Worksh. Computational Geometry, Brown Univ., 1998.
Disc. Comp. Geom. 23 (3): 305–323, 2000,
doi:10.1007/PL00009502.
We show that, for any set of \(n\) points in \(d\) dimensions, there exists a hyperplane with regression depth at least \(\lceil n/(d+1)\rceil\), 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 \(\lceil n/(d+1)\rceil\) 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.