Chung, Kuo-LiangKuo-LiangChungLin, Ferng-ChingFerng-ChingLinWEN-CHIN CHEN2020-05-042020-05-041990https://scholars.lib.ntu.edu.tw/handle/123456789/490339https://www.scopus.com/inward/record.uri?eid=2-s2.0-0025109234&doi=10.1145%2f255129.255147&partnerID=40&md5=ad00f6d526ccca358da45740a485b173We 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.Mathematical Techniques - Interpolation; B-Spline Interpolation; Supercomputing; Computer systems, Digitalconference paper10.1145/77726.255147https://www.scopus.com/inward/record.uri?eid=2-s2.0-0025109234&doi=10.1145%2f255129.255147&partnerID=40&md5=ad00f6d526ccca358da45740a485b173https://doi.org/10.1145/77726.255147