We show that, for any set of n points in d dimensions, there exists a hyper
plane 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 di
mensions there exists a point that cannot escape to infinity without,crossi
ng 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 com
putational complexity of regression depth problems.