# Algorthm: Given a set of points, width around line, find line to capture maximum points

I want to know if there is an algorithm for this problem.

I have a list of points given as (x,y) values and a given distance. I want to draw a line through the set of data points so that the size of the set of points that is within the given distance from the line is maximized. That is, this line

Does an algorithm for this problem exist?

• What have you tried? Where did you get stuck? I don't know if this is at all helpful, but my gut instinct says to look into the dual plane. – jmite Jul 31 '14 at 18:28
• What's your notion of distance from a point $P$ to a line $L$? Is it orthogonal distance (i.e., the length of the line segment that is orthogonal to $L$ and that connects $P$ to $L$)? Or is it shortest distance (i.e., the distance from $P$ to the closest point on $L$)? Or vertical distance (the length of the vertical line segment that connects $P$ to $L$), as in linear regression? This leads to several different variations on the problem, just as different definitions of residual lead to linear regression / PCA / etc. – D.W. Jul 31 '14 at 18:45
• If your notion of distance is orthogonal distance, you might want to look at the technique used in training SVMs to find a support vector with maximal margin; I suspect that might be applicable to your problem. – D.W. Jul 31 '14 at 18:50

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.

• Sorry for not mentioning, but I did in fact mean vertical distance, so this is exactly what I was looking for. – Onye Jul 31 '14 at 21:01