Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



A general framework for high-accuracy parametric interpolation

Authors: Knut Mørken and Karl Scherer
Journal: Math. Comp. 66 (1997), 237-260
MSC (1991): Primary 41A05, 41A10, 41A25, 65D05, 65D17; Secondary 65D10
MathSciNet review: 1372007
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper we establish a general framework for so-called parametric, polynomial, interpolation methods for parametric curves. In contrast to traditional methods, which typically approximate the components of the curve separately, parametric methods utilize geometric information (which depends on all the components) about the curve to generate the interpolant. The general framework suggests a multitude of interpolation methods in all space dimensions, and some of these have been studied by other authors as independent methods of approximation. Since the approximation methods are nonlinear, questions of solvability and stability have to be considered. As a special case of a general result, we prove that four points on a planar curve can be interpolated by a quadratic with fourth-order accuracy, if the points are sufficiently close to a point with nonvanishing curvature. We also find that six points on a planar curve can be interpolated by a cubic, with sixth-order accuracy, provided the points are sufficiently close to a point where the curvature does not have a double zero. In space it turns out that five points sufficiently close to a point with nonvanishing torsion can be interpolated by a cubic, with fifth-order accuracy.

References [Enhancements On Off] (What's this?)

  • 1. R. Bartels, J. Beatty, B. Barsky (1987): An Introduction to Splines for Use in Computer Graphics and Geometric Modeling. Los Altos, California: Morgan Kaufmann Publishers Inc. MR 89f:65018
  • 2. C. de Boor, K. Höllig, M. Sabin (1988): High accuracy geometric Hermite interpolation, Comput. Aided Geom. Design, 4:269-278. MR 90b:65014
  • 3. W. L. F. Degen (1992): Best approximation of parametric curves by splines. In: Mathematical Methods in Computer Aided Geometric Design II (T. Lyche, L. L. Schumaker, eds.). San Diego: Academic Press, pp. 171-184. MR 93e:41017
  • 4. L. F. Degen (1993): High accurate rational approximation of parametric curves. Comput. Aided Geom. Design, 10:293-313. MR 94i:65022
  • 5. T. Dokken, M. Dæhlen, T. Lyche, K. Mørken (1990): Good approximation of circles by curvature continuous Bézier curves. Comput. Aided Geom. Design, 7:33-41. MR 91j:65028
  • 6. E. F. Eisele (1994): Chebychev approximation of plane curves by splines, J. Approx. Theory, 76: 133-148. MR 95c:41024
  • 7. G. Farin (1993): Curves and Surfaces for CAGD. A Practical Guide. Third edition. Cambridge, Massachusetts: Academic Press Inc. MR 93k:65016
  • 8. M. Floater (1994): An $O(h^{2n})$ Hermite approximation for conic sections. Preprint, SINTEF-SI, Oslo.
  • 9. T. N. T. Goodman (1985): Properties of $\beta $-splines. J. Approx. Theory, 44:132-153. MR 87f:41020
  • 10. J. A. Gregory (1989): Geometric continuity. In: Mathematical Methods in CAGD (T. Lyche, L. L. Schumaker, eds.). Boston: Academic Press, pp. 353-371. MR 91d:65033
  • 11. R. Klass (1983): An offset spline approximation for plane cubic splines. Comp. Aided Design, 15:297-299.
  • 12. D. E. Knuth (1975): The Art of Computer Programming. Vol. 1, Fundamental Algorithms. Reading, Massachusetts: Addison Wesley Publishing Company. MR 51:14624
  • 13. M. A. Lachance, A. J. Schwartz (1991): Four point parabolic interpolation. Comput. Aided Geom. Design, 8:143-149. MR 92a:65045
  • 14. T. Lyche, K. Mørken (1994): A metric for parametric approximation. In: Curves and Surfaces in Geometric Design (P. J. Laurent, A. LeMéhauté, L. L. Schumaker, eds.). Wellesley, Massachusetts: A K Peters, Ltd., pp. 311-318. MR 95g:65027
  • 15. K. Mørken (1991): Best approximation of circle segments by quadratic Bézier curves. In: Curves and Surfaces (P. J. Laurent, A. Le Méhauté, L. L. Schumaker, eds.). Boston: Academic Press, pp. 331-336. CMP 91:17
  • 16. K. Mørken (1995): Parametric interpolation by quadratic polynomials in the plane. In: Mathematical Methods for Curves and Surfaces. Vanderbilt Univ. Press, Nashville, TN, pp. 385-402. MR 96h:65023
  • 17. A. Pinkus (1993): Uniqueness in vector valued approximation. J. Approx. Theory, 73:17-93. MR 94e:41047
  • 18. A. Rababah (1992): Approximation von Kurven mit Polynomen und Splines. Ph. D. thesis, Mathematisches Institut A, Universität Stuttgart.
  • 19. A. Rababah (1995): High order approximation method for curves. Comput. Aided Geom. Design, 12:89-102. MR 95m:65030
  • 20. R. Schaback (1989): Interpolation in $\mathbb {R} ^2$ by piecewise quadratic visually $C^2$ Bézier polynomials. Comput. Aided Geom. Design, 6:219-233. MR 90j:65020
  • 21. R. Schaback (1989): Convergence of planar curve interpolation schemes. In: Approximation Theory VI (C. Chui, L. L. Schumaker, J. Ward, eds.). Boston: Academic Press, pp. 581-584. CMP 91:07
  • 22. R. Schaback (1993): Planar curve interpolation by piecewise conics of arbitrary type. Constr. Approx., 9: 373-389. MR 94h:41006
  • 23. B. Sendov (1969/70): Parametric Approximation. Annuaire Univ. Sofia Fac. Math., 64:237-247. MR 46:7771
  • 24. M. Spivak (1979): A Comprehensive Introduction to Differential Geometry, Volume II. Second Edition. Wilmington, Delaware: Publish or Perish Inc. MR 82g:53003b
  • 25. J. Szabados (1972): On parametric approximation. Acta Math. Sci. Hung., 23:275-287. MR 52:8732

Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 41A05, 41A10, 41A25, 65D05, 65D17, 65D10

Retrieve articles in all journals with MSC (1991): 41A05, 41A10, 41A25, 65D05, 65D17, 65D10

Additional Information

Knut Mørken
Affiliation: Department of Informatics, University of Oslo, P. O. Box 1080 Blindern, N-0316 Oslo, Norway

Karl Scherer
Affiliation: Institut für Angewandte Mathematik, Universität Bonn, Wegelerstr. 6, D-53115 Bonn, Germany

Received by editor(s): December 15, 1994
Received by editor(s) in revised form: November 21, 1995, and January 26, 1996
Article copyright: © Copyright 1997 American Mathematical Society

American Mathematical Society