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

Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

• People
  • Personnel
  • Guests
  • Alumni
• Reports
  • Current Report
  • Report for 2023
  • Report for 2022
  • Previous Reports
• Research
  • Grants
  • Dissertations
  • Master/Bachelor Theses
  • Current Publications
  • Previous Publications
• Mittagsseminar
• Courses
• Thesis Topics
• Events
  • Workshops
    • Current
    • Previous
  • Social
    • SOLA
    • GREBGE
• 

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 dth 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 $\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 (or moving parallel to) at least $\lceil n/(d+1)\rceil$ 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

Imprint Disclaimer Copyright