Regression Depth and Center Points

David Eppstein, ICS, UC Irvine

We show that, for any set of *n* points in *d*
dimensions, there exists a hyperplane with regression depth at
least ceiling(*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
ceiling(*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.

This is joint work with Nina Amenta, Marshall Bern and Shang-Hua Teng.