Algorthm: Given a set of points, width around line, find line to capture maximum points
If your notion of distance is "vertical distance", similar to how residuals are computed during ordinary linear regression, this problem can be solved with linear programming.

Let $y=ax+b$ be the equation of the desired line; here $a,b$ are unknowns.  Suppose we are given a list of points $(x_i,y_i)$.  The vertical distance from $(x_i,v_i)$ to the line $y=ax+b$ is

$$|ax_i+b-y_i|.$$

Suppose we want this distance to be at most $d$, where $d$ is given.  In other words, we want

$$|ax_i+b-y_i| \le d.$$

This is equivalent to

$$y_i-d \le ax_i+b \le y_i+d,$$

which gives two linear inequalities.  (Recall that $x_i,y_i,d$ are known, and $a,b$ are unknown.)  Given $k$ points, you get $2k$ linear inequalities.  Now you can use linear programming to find $a,b$ that satisfy all of these linear inequalities.

You can even find the minimal value of $d$ such that such a line exists.  Simply treat $d$ as an additional unknown, and minimize $d$ subject to the $2k$ linear inequalities above.