Time complexity of simple linear regression in $L_1$ norm I come from a computer science background. I'm considering simple linear regression using $L_1$ distance.
We are given points $(x_1,y_1),\ldots,(x_n,y_n)\in \mathbb{R}^2$. We are interested in finding a line $f(x) = ax+b$, such that 
$$\sum_{i=1}^n |y_i - f(x_i)|$$
is minimized.
I did some initial literature search, and it seems people solve the problem using linear programming.
I am interested in finding the fastest algorithm in terms of the number of points. That is, I'm looking for references that looks like the following

Simple linear regression in $L_1$ norm can be solved in $O(T(n))$ time,
  where $n$ is the number of points.

 A: There is a $O(n^2)$ running time algorithm.
It is fairly easy to derive: There exists an optimal line that contains one of the given points (in fact, at least 2 points). There exists a $O(n)$ time algorithm to decide the best line that goes through a given point. Basically a weighted median computation. Together, it implies a $O(n^2)$ running time algorithm.
The first paper I know that uses this idea is the following. 

Bloomfield,
  Peter; Steiger, William, Least absolute deviations
  curve-fitting, SIAM J. Sci.
  Stat. Comput. 1, 290-301 (1980).
  ZBL0471.65007.

Edit 1:
Using advanced tools from computational geometry, one can improve the running time to $\tilde{O}(n^{4/3})$. 
Edit 2:
There is a paper that gives a $O(n\log^2 n)$ time algorithm.

Megiddo, Nimrod; Tamir,
  Arie, Finding least-distance
  lines, SIAM J. Algebraic
  Discrete Methods 4, 207-211 (1983).
  ZBL0517.05007.

There is another paper which I still have to verify, that explains $O(n)$ time is possible. In fact, it seems that $L_1$ linear regression in $d$ dimensions can be solved in $O(n)$ time if $d$ is a constant.

Zemel, Eitan, An O(n) algorithm for the linear multiple choice knapsack problem and related problems, Inf. Process. Lett. 18, 123-128 (1984). ZBL0555.90069.

