An optimal algorithm for expanding the composition of polynomials

ABSTRACT

A runtime analysis is made of a previously published algorithm for polynomial composition. The relationship between this composition algorithm and Sablonnie`re's algorithm is explored. This composition algorithm is then made optimal aby first performing a change of basis.

REFERENCES

• 1: BARRY, P. AND GOLDMAN, R. 1993. Knot insertion algorithms. In Knot Insertion and Deletion Algorithms for B-Spline Curves and Surfaces, SIAM, Philadelphia, 89-133.
• 2: DE BOOR, C. 1987. B-form basics. In Geometric Modeling: Algorithms and New Trends, G. Farin, ed., SIAM, Philadelphia, 131-148.
• 3: Tony D. DeRose, Composing Bézier simplexes, ACM Transactions on Graphics (TOG), v.7 n.3, p.198-221, July 1988 [doi>10.1145/44479.44482]
• 4: DEROSE, T. D. 1989. A coordinate-free approach to geometric programming. In Math for Siggraph. Siggraph Course Notes #23, 1989. Also available as Tech. Rep. No. 89-09-16, Department of Computer Science and Engineering, University of Washington, Seattle, WA (Sept.).
• 5: Tony D. DeRose , Ronald N. Goldman , Hans Hagen , Stephen Mann, Functional composition algorithms via blossoming, ACM Transactions on Graphics (TOG), v.12 n.2, p.113-135, April 1993 [doi>10.1145/151280.151290]
• 6: G. Farin, Curves and surfaces for computer aided geometric design, Academic Press Professional, Inc., San Diego, CA, 1990
• 7: MANN, S. AND LIU, W. 1995. An analysis of polynomial composition algorithms. Tech. Rep. CS-95-24, University of Waterloo, Waterloo, Ontario.
• 8: RAMSHAW, L. 1987. Blossoming: A connect-the-dots approach to splines. Tech. Rep. 19, Digital Systems Research Center, Palo Alto, CA.
• 9: SABLONNII~RE, P. 1978. Spline and B~zier polygons associated with a polynomial spline curve. Comput. Aided Des. 10, 4, 257-261.
• 10: SHOEMAKE, K. 1995. Efficient de Casteljau indexing. In preparation, 1995.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials

  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Algorithms, Design, Performance

Keywords:
blossoming, polynomial compostion, simplices