0
$\begingroup$

One can use least squares to fit a line to a set of points. However, these lines lack "thickness". (When I say "thickness", I refer to the orthogonal distance below and above the line.)

In my case, I wish to find the line of best fit with a "thickness" of 10 units. When I do regular line fitting using least squares with my data (shown below), this is the result (**I forced the intercept to be 0). I imagine that if the line had "thickness", the slope would change so that the line would pass through more-so the middle of the points.

For reproducibility, here are the coordinates of the points (the units are pixels):

    X   Y
0   -22.354813  42.107771
1   -24.767070  42.217283
2   -21.067303  40.581409
3   -18.098338  39.008191
4   -15.104359  39.459893
5   -11.859293  41.350605
6   -9.556148   42.072946
7   -6.946657   41.880829
8   -3.682567   40.867157
9   -4.032155   36.810784
10  -4.179892   32.834570
11  -5.270855   28.930028
12  -6.358178   25.024957
13  -8.509716   21.749395
14  -9.933444   18.156531
15  -13.534608  16.444366
16  -12.561564  17.263768
17  -10.248685  20.476541
18  -7.303676   23.248577
19  -4.566318   26.302741
20  -1.008366   28.056100
21  1.868756    30.946956
22  5.946280    31.326912
23  10.020591   31.741658
24  12.450070   28.980872
25  12.468064   24.915211
26  11.058997   21.056885
27  9.100764    17.539827
28  7.283052    13.935445
29  4.636873    12.192688
30  3.557589    8.770284
31  1.859458    5.091591
32  -0.440041   2.485075
33  0.000000    0.000000
$\endgroup$
0
1
$\begingroup$

Let $m$ be the slope, and let $u(x)=5+m x$ and $\ell(x)=-5+m x$ be the upper and lower boundaries of the line, respectively. You want to minimize $$\sum_i \left(\max(y_i - u(x_i), \ell(x_i) - y_i, 0)\right)^2.$$ You can solve this via quadratic programming by introducing an error variable $e_i \ge 0$ and minimizing the sum of squares $\sum_i e_i^2$ subject to linear constraints \begin{align} e_i &\ge y_i - u(x_i) &&\text{for all $i$}\\ e_i &\ge \ell(x_i) - y_i &&\text{for all $i$}\\ \end{align} The resulting optimal slope for your data is $m^*= -1.2678$. enter image description here


For the case of orthogonal thickness $10$, the $y$-intercept $b$ is $5\sqrt{m^2+1}$ instead of $5$, so let $u(x)=b+m x$ and $\ell(x)=-b+m x$ be the upper and lower boundaries of the line, respectively. You want to minimize $$\sum_i \left(\max(y_i - u(x_i), \ell(x_i) - y_i, 0)\right)^2.$$ You can solve this via nonlinear programming by introducing an error variable $e_i \ge 0$ and minimizing the sum of squares $\sum_i e_i^2$ subject to nonlinear constraints \begin{align} e_i &\ge y_i - u(x_i) &&\text{for all $i$}\\ e_i &\ge \ell(x_i) - y_i &&\text{for all $i$}\\ \end{align} The resulting optimal solution for your data is $(b^*,m^*)= (10.7877,-1.9118)$. enter image description here

$\endgroup$
4
  • $\begingroup$ I think you're on the right path, but will the thickness (the perpendicular distance between the two lines) be 10 units, regardless of the slope? I imagine for a very steep slope, the thickness will be thinner. $\endgroup$ – Captain Crime Bill Feb 13 at 4:37
  • $\begingroup$ If you are just looking for a method that works in practice, note that the vertical distance between the lines is proportional to the perpendicular distance for a given slope. So apply Rob's method repeatedly, with the vertical distance adjusted each time to give the desired perpendicular distance. If it converges, you have your answer. $\endgroup$ – Brendan McKay Feb 13 at 5:01
  • 2
    $\begingroup$ I updated my answer to enforce orthogonal (instead of vertical) thickness $10$. $\endgroup$ – RobPratt Feb 13 at 17:11
  • $\begingroup$ You might want to look at State Vector Machines (SVMs), which is an AI approach based on this idea, plus or minus. $\endgroup$ – eSurfsnake Feb 15 at 19:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.