Composition based staircase algorithm and constrained interpolation with boundary conditions (Q1572933)

In cubic spline interpolation with a convexity condition, the derivatives in the interpolation points have to satisfy a bidiagonal system of inequalities. Such weakly coupled systems of conditions appear in other situations as well. Suppose there is on top of these conditions an extra constraint expressed as a relation between the first and the last of the parameters of the system. In an abstract setting this means, given nonempty sets \(I_0,\ldots,I_n\), and binary relations \(W_i\subset I_{i-1}\times I_i\), and some constraint relation \(B\subset I_0\times I_n\), one has to find solutions \(p_i\) such that \((p_{i-1},p_i)\in W_i\), \(i=1,\ldots,n\) and \((p_0,p_n)\in B\). A two-stage algorithm is proposed. In a forward sweep, the composition \(R_n=W_1\cdot W_2\cdot \dots \cdot W_n\) is constructed; in a backward sweep a solution \((p_0,p_n)\in R_n\cap B\) is worked backward to find the other \(p_i\). This concept is applied to convex cubic spline interpolation. The extra constraint condition is of the form \(p_n=ap_0+b\). A nice geometric interpretation of the algorithm is given.