Maximum regression depth in the plane

The regression depth of a point in an arrangement of lines in the plane is the minimum number of lines that the point needs to cross to escape to infinity. It is called regression depth because the dual version (with points replaced by lines and vice versa) has to do with a robust estimator for a regression line defined by a set of points. See the work of Rousseeuw & Hubert, Statistics Group, University of Antwerp.

This applet, by Bettina Speckmann, implements a binary search algorithm that runs in O(n log^2 n) to compute the point of maximum depth. ( Paper in postscript, by van Kreveld, Mitchell, Rousseeuw, Sharir, Snoeyink, Speckmann, will appear in the 1999 ACM Symp on Comp Geom.)


Draw lines by clicking on two points that the line passes through. (You'll want to keep most of the intersections on screen; dragging the second point before you release may help.)

Clicking on MaxDepth steps through the binary search. The yellow search line sprouts red and green arrows indicating the topmost directions that define the regression depth in each cell that they intersect---from this information, the search can decide whether to continue to the left or right.

ResetMaxDepth allows you to add more lines and search again. ResetAll clears lines as well. Quit does nothing in the applet version.

The applet and accompanying paper are work-in-progress. Send mail to Bettina if you want updates or more information.