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.

1. 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
2. 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, https://doi.org/10.1016/0167-8396(87)90002-1
3. 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
4. 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, https://doi.org/10.1016/0167-8396(93)90043-3
5. 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, https://doi.org/10.1016/0167-8396(90)90019-N
6. Eberhard F. Eisele, Chebyshev approximation of plane curves by splines, J. Approx. Theory 76 (1994), no. 2, 133–148. MR 1268095, https://doi.org/10.1006/jath.1994.1010
7. 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
8. M. Floater (1994): An $O(h^{2n})$ Hermite approximation for conic sections. Preprint, SINTEF-SI, Oslo.
9. T. N. T. Goodman, Properties of 𝛽-splines, J. Approx. Theory 44 (1985), no. 2, 132–153. MR 794596, https://doi.org/10.1016/0021-9045(85)90076-0
10. John A. Gregory, Geometric continuity, Mathematical methods in computer aided geometric design (Oslo, 1988) Academic Press, Boston, MA, 1989, pp. 353–371. MR 1022718
11. R. Klass (1983): An offset spline approximation for plane cubic splines. Comp. Aided Design, 15:297-299.
12. 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
13. Michael A. Lachance and Arthur J. Schwartz, Four-point parabolic interpolation, Comput. Aided Geom. Design 8 (1991), no. 2, 143–149. MR 1107849, https://doi.org/10.1016/0167-8396(91)90039-E
14. 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
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. 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
17. Allan Pinkus, Uniqueness in vector-valued approximation, J. Approx. Theory 73 (1993), no. 1, 17–92. MR 1213123, https://doi.org/10.1006/jath.1993.1030
18. A. Rababah (1992): Approximation von Kurven mit Polynomen und Splines. Ph. D. thesis, Mathematisches Institut A, Universität Stuttgart.
19. Abedallah Rababah, High order approximation method for curves, Comput. Aided Geom. Design 12 (1995), no. 1, 89–102. MR 1311120, https://doi.org/10.1016/0167-8396(94)00004-C
20. Robert Schaback, Interpolation with piecewise quadratic visually 𝐶² Bézier polynomials, Comput. Aided Geom. Design 6 (1989), no. 3, 219–233. MR 1019424, https://doi.org/10.1016/0167-8396(89)90025-3
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. Robert Schaback, Planar curve interpolation by piecewise conics of arbitrary type, Constr. Approx. 9 (1993), no. 4, 373–389. MR 1237924, https://doi.org/10.1007/BF01204647
23. Blagovest Sendov, Parametric approximation, Annuaire Univ. Sofia Fac. Math. 64 (1969/70), 237–247 (1971) (Bulgarian, with English summary). MR 0308657
24. Michael Spivak, A comprehensive introduction to differential geometry. Vol. I, 2nd ed., Publish or Perish, Inc., Wilmington, Del., 1979. MR 532830
25. J. Szabados, On parametric approximation, Acta Math. Acad. Sci. Hungar. 23 (1972), 275–287. MR 387894, https://doi.org/10.1007/BF01896946