Given a set of points $v_1,\ldots,v_n\in\mathbb{R}^2$ I want to find a straight line $L\subset\mathbb{R}^2$ with minimal distance to the farthest point measured by the maximum norm, i.e. minimizing $$ \max_{i=1,\ldots,n}\mathrm{dist}_\infty(v_i, L), $$ where $\mathrm{dist}_\infty(v, L) = \inf_{p\in L}\|v-p\|_\infty$.
I have seen similar problems where $\mathrm{dist}_\infty(v, L)$ is replaced by something simpler, for example a vertical error $|y_i - f(x_i)|$. But the $\|\cdot\|_\infty$-distance is neither linear nor differentiable.
General purpose optimization algorithms do work of course, but I am interested in something more specialized (i.e. guarantees to calculate optimal solution), even more important would be estimates for the solution.
This $\max \mathrm{dist}_\infty$ combination seems to be quite uncommon and is hard to search for. Literature references are welcome, too.
