Boundary-valued shape-preserving interpolating splines

ABSTRACT

This article describes a general-purpose method for computing interpolating polynomial splines with arbitrary constraints on their shape and satisfying separable or nonseparable boundary conditions. Examples of applications of the related Fortran code are periodic shape-preserving spline intepolation and the construction of visually pleasing closed curves.

REFERENCES

• 1: Hiroshi Akima, Algorithm 433: interpolation and smooth curve fitting based on local procedures [E2], Communications of the ACM, v.15 n.10, p.914-918, Oct. 1972 [doi>10.1145/355604.355605]
• 2: Hiroshi Akima, Algorithm 697: univariate interpolation that has the accuracy of a third-degree polynomial, ACM Transactions on Mathematical Software (TOMS), v.17 n.3, p.367, Sept. 1991 [doi>10.1145/114697.116808]
• 3: Richard Ernest Bellman, Dynamic Programming, Dover Publications, Incorporated, 2003
• 4: DE BOOR, C. 1978. A Practical Guide to Splines. Springer-Verlag, Berlin, Germany.
• 5: Wolfgang Böhm , Gerald Farin , Jürgen Kahmann, A survey of curve and surface methods in CAGD, Computer Aided Geometric Design, v.1 n.1, p.1-60, July 1984 [doi>10.1016/0167-8396(84)90003-7]
• 6: A. K. Cline, Scalar- and planar-valued curve fitting using splines under tension, Communications of the ACM, v.17 n.4, p.218-220, April 1974 [doi>10.1145/360924.360971]
• 7: A. K. Cline, Six subprograms for curve fitting using splines under tension, Communications of the ACM, v.17 n.4, p.220-223, April 1974 [doi>10.1145/360924.360974]
• 8: Paolo Costantini, On monotone and convex spline interpolation, Mathematics of Computation, v.46 n.173, p.203-214, Jan. 1986 [doi>10.2307/2008224]
• 9: Paolo Costantini, An algorithm for computing shape-preserving interpolating splines of arbitrary degree, Journal of Computational and Applied Mathematics, v.22 n.1, p.89-136, April 1988 [doi>10.1016/0377-0427(88)90290-7]
• 10: COSTANTINI, P. 1990. On some recent methods for bivariate shape-preserving interpolation. In Multivariate Approximation and Interpolation. Birkh~iuser Verlag, Basel, Switzerland.
• 11: COSTANTINI, P. 1993. A general method for constrained curves with boundary conditions. In Multivariate Approximation: From CAGD to Wavelets. World Scientific Publishing, River Edge, N.J.
• 12: P. Costantini, Algorithm 770: BVSPIS—a package for computing boundary-valued shape-preserving interpolating splines, ACM Transactions on Mathematical Software (TOMS), v.23 n.2, p.252-254, June 1997 [doi>10.1145/264029.264059]
• 13: Paolo Constantini , Ferruccio Fontanella, Shape-preserving bivariate interpolation, SIAM Journal on Numerical Analysis, v.27 n.2, p.488-506, April 1990 [doi>10.1137/0727030]
• 14: Paolo Costantini , Carla Manni, A local scheme for bivariate co-monotone interpolation, Computer Aided Geometric Design, v.8 n.5, p.371-391, Nov. 1991 [doi>10.1016/0167-8396(91)90011-Y]
• 15: COSTANTINI, P. AND MORANDI, R. 1984. Monotone and convex cubic spline interpolation. CALCOLO 21,281-294.
• 16: Roger Delbourgo, Accurate C2 rational interpolants in tension, SIAM Journal on Numerical Analysis, v.30 n.2, p.595-607, April 1993 [doi>10.1137/0730029]
• 17: Gerald Farin, Curves and surfaces for computer aided geometric design: a practical guide, Academic Press Professional, Inc., San Diego, CA, 1988
• 18: David R Ferguson, Construction of curves and surfaces using numerical optimization techniques, Computer-Aided Design, v.18 n.1, p.15-21, Jan/Feb. 1986 [doi>10.1016/S0010-4485(86)80004-5]
• 19: FRITSCH, R. E. AND BUTLAND, J. 1984. A method for constructing local monotone piecewise cubic interpolants. SIAM J. Sci. Stat. Comput. 5, 300-304.
• 20: FRITSCH, R. E. AND CARLSON, R.E. 1980. Monotone piecewise cubic interpolation. SIAM J. Numer. Anal. 17, 238-246.
• 21: John A Gregory, Shape preserving spline interpolation, Computer-Aided Design, v.18 n.1, p.53-57, Jan/Feb. 1986 [doi>10.1016/S0010-4485(86)80012-4]
• 22: GREINER, H. 1991. A survey on univariate data interpolation and approximation by splines of given shape. Math. Comput. Model. 15, 97-106.
• 23: Hung T. Huynh, Accurate monotone cubic interpolation, SIAM Journal on Numerical Analysis, v.30 n.1, p.57-100, Feb. 1993 [doi>10.1137/0730004]
• 24: Panagiotis D. Kaklis , Nickolas S. Sapidis, Convexity-preserving interpolatory parametric splines of non-uniform polynomial degree, Computer Aided Geometric Design, v.12 n.1, p.1-26, Feb. 1995 [doi>10.1016/0167-8396(94)00029-R]
• 25: KAUFMAN, E. H. AND TAYLOR, G.D. 1994. Approximation and interpolation by convexitypreserving rational splines. Constr. Approx. 10, 275-283.
• 26: David F. McAllister , John A. Roulier, An Algorithm for Computing a Shape-Preserving Osculatory Quadratic Spline, ACM Transactions on Mathematical Software (TOMS), v.7 n.3, p.331-347, Sept. 1981 [doi>10.1145/355958.355964]
• 27: D. F. McAllister , J. A. Roulier, Algorithm 574: Shape-Preserving Osculatory Quadratic Splines [E1, E2], ACM Transactions on Mathematical Software (TOMS), v.7 n.3, p.384-386, Sept. 1981 [doi>10.1145/355958.355967]
• 28: MICCHELLI, C. A. AND UTRERAS, F.I. 1988. Smoothing and interpolation in a convex subset of Hilbert space. SIAM J. Sci. Stat. Comput. 9, 5, 728-746.
• 29: R. J. Renka, Algorithm 716; TSPACK: tension spline curve-fitting package, ACM Transactions on Mathematical Software (TOMS), v.19 n.1, p.81-94, March 1993 [doi>10.1145/151271.151277]
• 30: M. Sakai , J. W. Schmidt, Positive interpolation with rational splines, BIT, v.29 n.1, p.140-147, 1989 [doi>10.1007/BF01932711]
• 31: SCHMIDT, J.W. 1989. On Shape-Preserving Spline Interpolation: Existence Theorems and Determination of Optimal Splines. Approximation and function spaces, vol. 22. PWN-- Polish Scientific Publishers, Warsaw, Poland.
• 32: SCHWEIKERT, D.G. 1966. Interpolatory tension splines with automatic selection of tension factors. J. Math. Phys. 45, 312-317.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

General Terms:
Algorithms, Performance

Keywords:
Bernstein-Be´zier polynomials, dynamic programming, spline interpolation