Line Fitting

mediumFREELeast SquaresOptimizationCV: Model Fitting and Optimization

Implement a line fitting model using the least squares method to find the best-fit line $y = mx + b$ for a given set of points. This task involves minimizing the sum of squared residuals between observed points and predicted values.

The least squares approach is a fundamental concept in model fitting and optimization, aiming to find the optimal parameters that result in the smallest possible sum of squared errors. In this case, the goal is to determine the slope $m$ and intercept $b$ of the line that minimizes the sum of squared residuals $E = \sum_i (y_i - (mx_i + b))^2$ .

To achieve this, the process involves the following steps:

Calculate the necessary summations of $x$ , $y$ , $x^2$ , and $xy$ for the given points.
Use these summations to derive the parameters $m$ and $b$ . The key to this process lies in the mathematical formulation of the normal equations, which provide a way to solve for $m$ and $b$ .

E = \sum_i (y_i - (mx_i + b))^2

This technique is widely used in computer vision for tasks such as image processing and object detection.

Example

Input

fit_line([(0,0), (1,1), (2,2)])

Output

[1.0, 0.0]

Reasoning

points is a list of $n = 3$ coordinate pairs $(x_i, y_i)$ : $(0,0)$ , $(1,1)$ , $(2,2)$ . The output is the pair $[m, b]$ , slope first, then intercept.
The four sums the description mentions: $\sum x_i = 0+1+2 = 3$ , $\sum y_i = 3$ , $\sum x_i^2 = 0+1+4 = 5$ , $\sum x_i y_i = 0+1+4 = 5$ .
Setting the derivatives of $E$ with respect to $m$ and $b$ to zero gives the normal equations $\sum x_i y_i = m\sum x_i^2 + b\sum x_i$ and $\sum y_i = m\sum x_i + nb$ . With these numbers: $5 = 5m + 3b$ and $3 = 3m + 3b$ .
Subtracting the second from the first leaves $2 = 2m$ , so $m = 1$ ; then $3 = 3 + 3b$ gives $b = 0$ . Rounded to 4 decimal places that is [1.0, 0.0].
Notice every residual $y_i - (mx_i + b)$ is $0$ here, so $E = 0$ : the points lie exactly on $y = x$ . Noisy points give the line of smallest $E$ , with $E > 0$ .

Constraints

Return [m, b] rounded to 4 decimal places

Learn this in

Model Fitting and OptimizationCV Study Plan Linear AlgebraFoundations

More from CV: Model Fitting and Optimization

RANSAC Homography Estimationmedium RANSAC Line Fittingmedium RANSAC Line Fithard Line from Two Pointseasy Count Inlierseasy

Concept primer

You want to find the line $y = mx + b$ that best fits a set of points $(x_i, y_i)$ by minimizing the sum of squared vertical errors:

E(m,b) = \sum_i (y_i - (mx_i + b))^2.

This is a classic linear least squares problem, whose solution can be derived from the normal equations of linear regression.

1. Background Knowledge (Key Concepts)

Least squares idea You have noisy data points and want a model (here, a line) that explains them “on average” as well as possible. Least squares chooses parameters $m, b$ to minimize the sum of squared residuals (vertical differences between observed $y_i$ and predicted $\hat y_i = mx_i + b$ ). This gives a closed-form solution for linear models.
Linear model as matrix equation Write the model in vector/matrix form:

\mathbf{y} \approx X\boldsymbol{\theta}, \quad\text{where}\quad \boldsymbol{\theta} = \begin{bmatrix} m \\ b \end{bmatrix}, \; X= \begin{bmatrix} x_1 & 1 \\ x_2 & 1 \\ \vdots & \vdots \\ x_n & 1 \end{bmatrix}, \; \mathbf{y}= \begin{bmatrix} y_1 \\ y_2 \\ \vdots \\ y_n \end{bmatrix}.

The least squares solution minimizes $\|$ \mathbf{y} $- X\boldsymbol{$ \theta $}\|^2$ .

Normal equations Setting the gradient of the error to zero leads to the normal equations:

X^\top X \,\boldsymbol{\theta} = X^\top \mathbf{y}.

For a 2-parameter line, this is a $2\times 2$ linear system in $m$ and $b$ that you can solve analytically or numerically.

2. Algorithm / General Approach

For this kind of 1D line-fitting least squares problem, the general pattern is:

Set up the design matrix $X$ from your input data (one column for $x$ , one column of 1s for the intercept).
Form the normal equations $X^\top X \boldsymbol{$ \theta $} = X^\top y$ .
Solve the small linear system for $\boldsymbol{$ \theta $} = [m, b]^T$ .
Use $m$ and $b$ to define your fitted line.

In practice, for a simple line you can also derive explicit formulas for $m$ and $b$ using sums of $x_i, y_i, x_i^2, x_i y_i$ , but conceptually it’s the same as solving the normal equations.

3. Step-by-Step Strategy (Implementation View)

Assume you’re given arrays x[i], y[i] for $i = 1 \dots n$ .

A. Using explicit sums (common in coding problems)

Compute aggregate sums

$S_x =$ \sum $_i x_i$
$S_y =$ \sum $_i y_i$
$S_{xx} =$ \sum $_i x_i^2$
$S_{xy} =$ \sum $_i x_i y_i$

Compute denominator

$D = n S_{xx} - S_x^2$ .

Solve for parameters

$m = \dfrac{n S_{xy} - S_x S_y}{D}$
$b = \dfrac{S_y S_{xx} - S_x S_{xy}}{D}$

Return or print $m$ and $b$ as the result.

B. Using the normal equations formulation (for understanding)

Construct:

# Conceptually:
X = [[x1, 1],
[x2, 1],
...
[xn, 1]]
y = [y1, y2,..., yn]

Compute:

A = X^\top X,\quad c = X^\top y

(in code, these are just sum combinations as above). 3. Solve the 2×2 system $A$ \theta $= c$ for $\theta = [m, b]^T$ .

4. Common Pitfalls

Degenerate or nearly degenerate data
If all $x_i$ are identical, then the denominator $D$ becomes zero: a vertical line cannot be represented as $y = mx + b$ . You should handle this edge case explicitly if it can occur.
Integer vs float division
In many languages, dividing integers does integer division by default. Ensure you cast to floating point before division so $m$ and $b$ are not truncated.
Overflow / precision
For very large coordinates or many points, sums like $S_{xx}$ can get large. In typical coding problems this is usually within safe bounds, but be aware and use appropriate numeric types (e.g., double).
Off-by-one errors
Make sure your loop runs over all points, and that n is the actual number of points used in the sums.

5. Time & Space Complexity

Time complexity
You compute a constant number of sums in a single pass over the data.
Complexity: $O(n)$ where $n$ is the number of points.
Space complexity
If you just iterate over the points and maintain running sums, you use a constant amount of extra memory.
Complexity: $O(1)$ auxiliary space (aside from the input arrays).

solution.py

Python 3.13

Test results