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

Authors: Knut Mørken and Karl Scherer
Journal: Math. Comp. 66 (1997), 237-260
MSC (1991): Primary 41A05, 41A10, 41A25, 65D05, 65D17; Secondary 65D10
DOI: https://doi.org/10.1090/S0025-5718-97-00796-5
MathSciNet review: 1372007
Full-text PDF Free Access

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.

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 https://doi.org/10.1016/0167-8396%2887%2990002-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 https://doi.org/10.1016/0167-8396%2893%2990043-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 https://doi.org/10.1016/0167-8396%2890%2990019-N
Eberhard F. Eisele, Chebyshev approximation of plane curves by splines, J. Approx. Theory 76 (1994), no. 2, 133–148. MR 1268095, DOI https://doi.org/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 https://doi.org/10.1016/0021-9045%2885%2990076-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 Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Volume 1: Fundamental algorithms; Addison-Wesley Series in Computer Science and Information Processing. 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 https://doi.org/10.1016/0167-8396%2891%2990039-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 https://doi.org/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 https://doi.org/10.1016/0167-8396%2894%2900004-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 https://doi.org/10.1016/0167-8396%2889%2990025-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 https://doi.org/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 https://doi.org/10.1007/BF01896946