In this chapter we present an first algorithm to find the deepest regression line, which is the fit with maximal regression depth for a given dataset $Z_n = \{(x_i, y_i), i = 1,...,n \} \subset \rm I\!R^2$

Sort all element of $Z_n$ by their $x$ coordinate such that $x_1 < x_2 < ... < x_n$

For each pair $ij$ such that $0 < i < j \le n$:

Find the line $l_{ij}$ that intersects with observations $i$ and $j$

Use the algorithm defined in chapter two to compute $r_{ij} = rdepth(l_{ij}, Z_n)$ (without the sorting wich is already done)

If $r_{ij}$ is greater than the regression depth of the temporary solution, keep $l_{ij}$ as a new temporary solution.

Return the $l_{ij}$ that has the greatest regression depth, it is the deepest regression line.

Given the previous algorithm, one can find the deepest regression line of a dataset $Z_n$ in $\mathcal{O}(n^3)$.

Step one consist in a sorting, wich can be done by a efficient sorting algorithm (e.g. Quicksort) in $\mathcal{O}(n \log (n))$

Going through all the $ij$ pairs is done in $\mathcal{O}(n^2)$

The algorithm used to compute rdepth, performs in $\mathcal{O}(n)$

So we conclude thaht the algorithm presented in this chapter to compute the deepest regression line performs in $\mathcal{O}(n \log(n) + n^3) = \mathcal{O}(n^3)$.

Example

The following application allows you to find the deepest regression line of a set of points. Some random points can also be added to ease the use of the application.