Publications Java Demos Rectangular Cartograms Kinetic Collision Detection Tripod Maximum Regression Depth Rectangular Cartograms

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 and Hubert, Robust & Applied Statistics Group, University of Antwerp.

This applet implements a binary search algorithm that runs in O(n log2n) to compute a point of maximum depth. It also identifies all deepest points in an arrangement of lines which can take the form of a single point, a polygon or a single chain of edges and some isolated points.

 Efficient Algorithms for Maximum Regression Depth M. van Kreveld, J.S.B. Mitchell, P. Rousseeuw, M. Sharir, J. Snoeyink, and B. Speckmann. Proc. 15th ACM Symposium on Computational Geometry (SoCG), pp. 31-40, 1999.

 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, otherwise you can always use the scrollbars to navigate through your arrangement. Clicking on MaxDepth will compute all points of maximum depth. The status line at the bottom of your webbrowser will display a message about the structure of the polygon, points and/or edges of maximum depth. The yellow search line indicates where the binary search stopped, the blue polygon is the first potential polygon of maximum depth, the pink vertices are points of maximum depth and the red edges are part of a chain of maximum depth edges. The red and green arrows indicate top directions. MaxDepth (step) 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.