## Deepest regression line

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$

#### Algorithm

Algorithm: Deepest regression line
Input:
• $Z_n = \{(x_i, y_i), i = 1,...,n \} \subset \rm I\!R^2$
Steps:
1. Sort all element of $Z_n$ by their $x$ coordinate such that $x_1 < x_2 < ... < x_n$
2. 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.
3. 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.