Cost-optimal parallel B-spline interpolations.

We show how to transform the B-spline curve and surface fitting problems into suffix computations of continued fractions. Then a parallel substitution scheme is introduced to compute the suffix values on a newly proposed mesh-of-unshuffle network. The derived parallel algorithm allows the curve interpolation through n points to be solved in O(log n) time using Θ(n/log n) processors and allows the surface interpolation through m × n points to be solved in O(log m log n) time using Θ(mn/(log m log n)) processors. Both interpolation algorithms are cost-optimal for their respective problems. Besides, the surface fitting problem can be even faster solved in O(log m + log n) time if Θ(mn) processors are used in the network.