# 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.)

### Instructions

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.