A quadratic-time algorithm for smoothing interval functions (Q1921294)

The authors consider the following problem: given \(n-1\) intervals \(X_1, \dots, X_{n-1}\), find \(n-1\) numbers \(x_i\), \(i=1,\dots,n-1\), such that \(x_i\) belongs to \(X_i\) for \(i=1, \dots, n-1\) and the sum of the squares of the differences \(x_i-x_{i-1}\), \(i=1, \dots, n\), is minimal \((x_0 = x_n=0)\). A quadratic-time algorithm for the solution of this problem is proposed.