Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Prof. Emo Welzl and Prof. Bernd Gärtner

**Regression Depth and Center Points
**

**
Marshall Bern, Xerox PARC**

The regression depth of a hyperplane *P* in a configuration of points
in *$Rd$*
is the minimum number of points that *P* must pass through
in moving to vertical (that is, parallel to the *d*th axis).
Regression depth, a notion due to Peter Rousseeuw,
is a purely combinatorial and affine-invariant measure
of the quality of a regression hyperplane.

In this talk, we show that
for any set of *n* points in *d* dimensions, there exists a
hyperplane with regression depth at least
,
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
(or moving parallel to) at least
hyperplanes.

To prove the result, we introduce the ``crossing distance'' between a point and a hyperplane in an arrangement of points, and show how to reformulate both the classical notion of center points and the novel notion of regression depth in terms of crossing distance. We then show that the two notions are in fact connected, and prove the existence of a high-regression-depth hyperplane by an application of Brouwer's fixed point theorem.

[Joint work with Nina Amenta, David Eppstein, and Shang-Hua Teng]

Back