A thesis submitted in partial fulfillment of the requirements for the degree of Master of Science

Thesis (M.Sc.) - Asian Institute of Technology, 1989

This thesis presents, in a unified approach, the important properties of B-splines and the important computational problems involved in working with them. In this framework, B-spline basis is used to define a curve and the knot insertion strategy is used to add the flexibility of a curve so as to provide an intuitive feel for how to change or control its shape. Important algorithms for curve generation that use divided difference definition, recursive definition and repeated linear interpolation of point such as deBoor algorithm have been implemented, thoroughly tested and compared in terms of speed, memory usage, time complexity in the worst case and program complexity. This process was also applied to the knot insertion strategy that uses Oslo algorithm 1, Oslo algorithm 2 and Insertion algorithm. For curve generation, the experimental results shown that recursive definition has the speed and resource utilization at the acceptable level. deBoor algorithm is the best choice for those applications where the speed is crucial for attaining the throughput on schedule but there is sufficient memory space, while divided difference method is suggested when there is limited memory space but the speed is not so critical. For knot insertion, in terms of efficiency, the Insertion algorithm ranks first, Oslo algorithm 1, the second and Oslo algorithm 2, the third. However, the more efficiency the algorithm is, the more difficult programming task it requires.