A general framework for high-accuracy parametric interpolation

Mørken, Knut; Scherer, Karl

doi:10.1090/S0025-5718-97-00796-5

A general framework for high-accuracy parametric interpolation
HTML articles powered by AMS MathViewer

by Knut Mørken and Karl Scherer PDF

Math. Comp. 66 (1997), 237-260 Request permission

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

Richard H. Bartels, John C. Beatty, and Brian A. Barsky, An introduction to splines for use in computer graphics and geometric modeling, Morgan Kaufmann, Palo Alto, CA, 1987. With forewords by Pierre Bézier and A. Robin Forrest. MR 919732
Carl de Boor, Klaus Höllig, and Malcolm Sabin, High accuracy geometric Hermite interpolation, Comput. Aided Geom. Design 4 (1987), no. 4, 269–278. MR 937366, DOI 10.1016/0167-8396(87)90002-1
W. L. F. Degen, Best approximations of parametric curves by splines, Mathematical methods in computer aided geometric design, II (Biri, 1991) Academic Press, Boston, MA, 1992, pp. 171–184. MR 1172801
W. L. F. Degen, High accurate rational approximation of parametric curves, Comput. Aided Geom. Design 10 (1993), no. 3-4, 293–313. Free-form curves and free-form surfaces (Oberwolfach, 1992). MR 1235159, DOI 10.1016/0167-8396(93)90043-3
Tor Dokken, Morten Dæhlen, Tom Lyche, and Knut Mørken, Good approximation of circles by curvature-continuous Bézier curves, Comput. Aided Geom. Design 7 (1990), no. 1-4, 33–41. Curves and surfaces in CAGD ’89 (Oberwolfach, 1989). MR 1074597, DOI 10.1016/0167-8396(90)90019-N
Eberhard F. Eisele, Chebyshev approximation of plane curves by splines, J. Approx. Theory 76 (1994), no. 2, 133–148. MR 1268095, DOI 10.1006/jath.1994.1010
Gerald Farin, Curves and surfaces for computer aided geometric design, 3rd ed., Computer Science and Scientific Computing, Academic Press, Inc., Boston, MA, 1993. A practical guide; With 1 IBM-PC floppy disk (5.25 inch; DD). MR 1201325
M. Floater (1994): An $O(h^{2n})$ Hermite approximation for conic sections. Preprint, SINTEF-SI, Oslo.
T. N. T. Goodman, Properties of $\beta$-splines, J. Approx. Theory 44 (1985), no. 2, 132–153. MR 794596, DOI 10.1016/0021-9045(85)90076-0
John A. Gregory, Geometric continuity, Mathematical methods in computer aided geometric design (Oslo, 1988) Academic Press, Boston, MA, 1989, pp. 353–371. MR 1022718
R. Klass (1983): An offset spline approximation for plane cubic splines. Comp. Aided Design, 15:297–299.
Donald E. Knuth, The art of computer programming, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Volume 1: Fundamental algorithms. MR 0378456
Michael A. Lachance and Arthur J. Schwartz, Four-point parabolic interpolation, Comput. Aided Geom. Design 8 (1991), no. 2, 143–149. MR 1107849, DOI 10.1016/0167-8396(91)90039-E
T. Lyche and K. Mørken, A metric for parametric approximation, Curves and surfaces in geometric design (Chamonix-Mont-Blanc, 1993) A K Peters, Wellesley, MA, 1994, pp. 311–318. MR 1302212
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.
Knut Mørken, Parametric interpolation by quadratic polynomials in the plane, Mathematical methods for curves and surfaces (Ulvik, 1994) Vanderbilt Univ. Press, Nashville, TN, 1995, pp. 385–402. MR 1356983
Allan Pinkus, Uniqueness in vector-valued approximation, J. Approx. Theory 73 (1993), no. 1, 17–92. MR 1213123, DOI 10.1006/jath.1993.1030
A. Rababah (1992): Approximation von Kurven mit Polynomen und Splines. Ph. D. thesis, Mathematisches Institut A, Universität Stuttgart.
Abedallah Rababah, High order approximation method for curves, Comput. Aided Geom. Design 12 (1995), no. 1, 89–102. MR 1311120, DOI 10.1016/0167-8396(94)00004-C
Robert Schaback, Interpolation with piecewise quadratic visually $C^2$ Bézier polynomials, Comput. Aided Geom. Design 6 (1989), no. 3, 219–233. MR 1019424, DOI 10.1016/0167-8396(89)90025-3
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.
Robert Schaback, Planar curve interpolation by piecewise conics of arbitrary type, Constr. Approx. 9 (1993), no. 4, 373–389. MR 1237924, DOI 10.1007/BF01204647
Blagovest Sendov, Parametric approximation, Annuaire Univ. Sofia Fac. Math. 64 (1969/70), 237–247 (1971) (Bulgarian, with English summary). MR 0308657
Michael Spivak, A comprehensive introduction to differential geometry. Vol. I, 2nd ed., Publish or Perish, Inc., Wilmington, Del., 1979. MR 532830
J. Szabados, On parametric approximation, Acta Math. Acad. Sci. Hungar. 23 (1972), 275–287. MR 387894, DOI 10.1007/BF01896946