Introduction

Segmented least squares fits several straight-line segments to ordered data instead of forcing one line across the whole dataset. The goal is to balance fit quality against model complexity by adding a penalty for each segment.

Dynamic programming is the standard exact solution because the best segmentation ending at point j can be built from the best segmentation ending earlier plus the cost of fitting one final segment. That optimal-substructure property makes the recurrence natural and efficient.

Problem Setup

Assume the points are ordered by x coordinate as (x1, y1) through (xn, yn). For any interval from i to j, define:

• 'error[i][j] as the squared error of the best-fit line through points i through j.'
• 'C as the fixed penalty for introducing one segment.'

Then the objective is to minimize total line-fit error plus C times the number of segments.

The recurrence is:

dp[j] = min over i from 1 to j of dp[i - 1] + error[i][j] + C

with dp[0] = 0.

This says: if the last segment starts at i and ends at j, then the total best cost up to j is the best cost before i plus the cost of fitting that final segment.

A Runnable Python Implementation

The code below computes line-fit error for every interval, fills the dynamic-programming table, and reconstructs the chosen segments.

1from math import inf
2
3
4def fit_error(points, i, j):
5    segment = points[i:j + 1]
6    n = len(segment)
7    xs = [p[0] for p in segment]
8    ys = [p[1] for p in segment]
9
10    sum_x = sum(xs)
11    sum_y = sum(ys)
12    sum_xx = sum(x * x for x in xs)
13    sum_xy = sum(x * y for x, y in segment)
14
15    denominator = n * sum_xx - sum_x * sum_x
16    if denominator == 0:
17        m = 0.0
18    else:
19        m = (n * sum_xy - sum_x * sum_y) / denominator
20    b = (sum_y - m * sum_x) / n
21
22    return sum((y - (m * x + b)) ** 2 for x, y in segment)
23
24
25def segmented_least_squares(points, penalty):
26    n = len(points)
27    error = [[0.0] * n for _ in range(n)]
28    for i in range(n):
29        for j in range(i, n):
30            error[i][j] = fit_error(points, i, j)
31
32    dp = [0.0] + [inf] * n
33    parent = [-1] * (n + 1)
34
35    for j in range(1, n + 1):
36        for i in range(1, j + 1):
37            cost = dp[i - 1] + error[i - 1][j - 1] + penalty
38            if cost < dp[j]:
39                dp[j] = cost
40                parent[j] = i - 1
41
42    segments = []
43    idx = n
44    while idx > 0:
45        start = parent[idx]
46        segments.append((start, idx - 1))
47        idx = start
48
49    segments.reverse()
50    return dp[n], segments
51
52
53points = [(1, 1.2), (2, 2.0), (3, 2.9), (4, 8.1), (5, 9.0), (6, 10.2)]
54cost, segments = segmented_least_squares(points, penalty=2.0)
55print(round(cost, 3))
56print(segments)

This implementation is clear rather than heavily optimized. It is good for understanding the recurrence and for moderate input sizes.

Why the Algorithm Works

Every optimal segmentation has a final segment. If that final segment begins at i, then everything before i must also be optimally segmented. Otherwise, replacing the prefix with a cheaper segmentation would improve the whole solution, contradicting optimality.

That is the exact reason dynamic programming applies. Once error[i][j] is known for all intervals, each dp[j] only depends on previously solved subproblems.

The usual time complexity is O(n^3) for a straightforward implementation, because there are O(n^2) intervals and each naive error computation may scan O(n) points. With prefix sums, the line parameters and errors can be precomputed more efficiently, often reducing the practical cost to O(n^2) after preprocessing.

Choosing the Penalty

The penalty term controls the tradeoff between accuracy and overfitting.

• Small penalty means more segments and tighter local fit.
• Large penalty means fewer segments and smoother approximation.

There is no universal best value. In a compression problem you may care about model size, while in a signal-fitting task you may care more about fidelity. Treat the penalty as a modeling decision, not a purely mechanical constant.

Common Pitfalls

A common mistake is applying the algorithm to unsorted points. Segmented least squares assumes an ordered sequence along the x axis. If the points are not sorted, the resulting segments are meaningless.

Another issue is recomputing regression statistics from scratch inside every inner loop without understanding the cost. That is fine for explanation code but not for large datasets.

Developers also sometimes omit the segment penalty. Without it, the trivial best solution is often one segment per point, which defeats the purpose of the model.

Finally, watch out for degenerate intervals where all x values are identical. The slope formula needs special handling in that case.

Summary

• Segmented least squares fits multiple lines while penalizing extra segments.
• Dynamic programming works because the optimal solution has an optimal prefix.
• The key recurrence is dp[j] = min(dp[i - 1] + error[i][j] + penalty).
• Straightforward implementations are easy to understand but can be cubic in time.
• The penalty term controls the balance between smoothness and fit accuracy.