← All problems

Rousseeuw and Hubert's conjecture on maximum regression depth

28 years old · traced to

Let SS be a set of nn points in dd-dimensional space. The regression depth of a hyperplane is the minimum number of points intersected by the hyperplane as it undergoes a continuous motion from its initial position to vertical. Rousseeuw and Hubert's conjecture. For every dd-dimensional set of nn points, there exists a hyperplane having regression depth

⌈nd+1⌉.\left\lceil\frac{n}{d+1}\right\rceil.

The conjecture asks for the higher-dimensional analogue of the optimal planar bound, and is motivated by the relation between regression depth and center-point phenomena.

References

Status

  • Solved: Nina Amenta, Marshall Bern, David Eppstein, and Shang-Hua Teng. Regression Depth and Center Points (Discrete & Computational Geometry 23(3):305–323, 2000) https://arxiv.org/abs/cs/9809037

Source: Nina Amenta, Marshall Bern, David Eppstein and Shang-Hua Teng, “Regression Depth and Center Points”, arXiv:cs/9809037 (1999).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.