Abstract
We describe local Lagrange interpolation methods based onC1 cubic splines on triangulations obtained from arbitrary strictly convex quadrangulations by adding one or two diagonals. Our construction makes use of a fast algorithm for coloring quadrangulations, and the overall algorithm has linear complexity while providing optimal order approximation of smooth functions.
This is a preview of subscription content,log in via an institution to check access.
Access this article
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
Price includes VAT (Japan)
Instant access to the full article PDF.
Similar content being viewed by others
Explore related subjects
Discover the latest articles and news from researchers in related subjects, suggested using machine learning.References
P. Bose and G.T. Toussaint, Characterizing and efficiently computing quadrangulations of planar point sets, Comput. Aided Geom. Design 14 (1997) 763–785.
G. Chartrand, P. Geller and S. Hedetniemi, A generalization of the chromatic number, Proc. Cambridge Phil. Soc. 64 (1968) 265–271.
L. Cowen, W. Goddard and C.E. Jesurum, Coloring with defect, in:Proc. of the 8th ACM-SIAM Symposium on Discrete Algorithms, 1997, pp. 548–557.
O. Davydov and G. Nürnberger, Interpolation byC1 splines of degreeq ≥ 4 on triangulations, J. Comput. Appl. Math. 126 (2000) 159–183.
O. Davydov, G. Nürnberger and F. Zeilfelder, Cubic spline interpolation on nested polygon triangulations, in:Curve and Surface Fitting, eds. A. Cohen, C. Rabut and L.L. Schumaker (Vanderbilt Univ. Press, Nashville, 2000) pp. 161–170.
O. Davydov, G. Nürnberger and F. Zeilfelder, Bivariate spline interpolation with optimal approximation order, Constr. Approx. 17 (2001) 181–208.
C. de Boor, B-form basics, in:Geometric Modeling, ed. G. Farin (SIAM, Philadelphia, PA, 1987) pp. 131–148.
C. de Boor and K. Höllig, Approximation order from bivariateC1-cubics: a counterexample, Proc. Amer. Math. Soc. 87 (1983) 649–655.
G. Farin, Triangular Bernstein-Bézier patches, Comput. Aided Geom. Design 3 (1986) 83–127.
B. Fraeijs de Veubeke, A conforming finite element for plate bending, J. Solids Struct. 4 (1968) 95–108.
T.R. Jensen and B. Toft,Graph Coloring Problems (Wiley, New York, 1995).
M.-J. Lai, Scattered data interpolation and approximation using bivariateC1 piecewise cubic polynomials, Comput. Aided Geom. Design 13 (1996) 81–88.
M.-J. Lai and L.L. Schumaker, On the approximation power of bivariate splines, Adv. Comput. Math. 9 (1998) 251–279.
M.-J. Lai and L.L. Schumaker, Scattered data interpolation usingC2 supersplines of degree six, SIAM J. Numer. Anal. 34 (1997) 905–921.
M.-J. Lai and L.L. Schumaker, On the approximation power of splines on triangulated quadrangulations, SIAM J. Numer. Anal. 36 (1999) 143–159.
M.-J. Lai and L.L. Schumaker, Quadrilateral macro-elements, SIAM J. Math. Anal. 33 (2002) 1107–1116.
L. Lovàsz, On decomposition of graphs, Studia Sci. Math. Hungar. 1 (1966) 237–238.
R. Mabry, Louisiana State University, Shreveport, USA, Private communication.
G. Nürnberger and Th. Rießinger, Lagrange and Hermite interpolation by bivariate splines, Numer. Funct. Anal. Optim. 13 (1992) 75–96.
G. Nürnberger and Th. Rießinger, Bivariate spline interpolation at grid points, Numer. Math. 71 (1995) 91–119.
G. Nürnberger, L.L. Schumaker and F. Zeilfelder, Local Lagrange interpolation by bivariateC1 cubic splines, in:Mathematical Methods for Curves and Surfaces III, Oslo, 2000, eds. T. Lyche and L.L. Schumaker (Vanderbilt Univ. Press, Nashville, 2000) pp. 393–404.
G. Nürnberger, L.L. Schumaker and F. Zeilfelder, Lagrange interpolation byC1 cubic splines on triangulations of separable quadrangulations, in:Approximation Theory, Vol. X:Splines, Wavelets, and Applications, eds. C.K. Chui, L.L. Schumaker and J. Stöckler (Vanderbilt Univ. Press, Nashville, 2002) pp. 405–424.
G. Nürnberger and F. Zeilfelder, Interpolation by spline spaces on classes of triangulations, J. Comput. Appl. Math. 119 (2000) 347–376.
G. Nürnberger and F. Zeilfelder, Developments in bivariate spline interpolation, J. Comput. Appl. Math. 121 (2000) 125–152.
G. Nürnberger and F. Zeilfelder, Local Lagrange interpolation by cubic splines on a class of triangulations, in:Trends in Approximation Theory, eds. K. Kopotun, T. Lyche and M. Neamtu (Vanderbilt Univ. Press, Nashville, 2001) pp. 341–350.
G. Nürnberger and F. Zeilfelder, Local Lagrange interpolation on Powell-Sabin triangulations and terrain modelling, in:Recent Progress in Multivariate Approximation, eds. W. Haußmann, K. Jetter and M. Reimer, International Series of Numerical Mathematics, Vol. 137 (Birkhäuser, Basel, 2001) pp. 227–244.
G. Nürnberger and F. Zeilfelder, Lagrange interpolation by bivariateC1 splines with optimal approximation order, Adv. Comput. Math. 21 (2004) 381–419.
G. Sander, Bornes supérieures et inférieures dans l'analyse matricielle des plaques en flexion-torsion, Bull. Soc. Roy. Sciences Liège 33 (1964) 456–494.
L.L. Schumaker, Fitting surfaces to scattered data, in:Approximation Theory, Vol. II, eds. G.G. Lorentz et al. (1976) pp. 203–268.
D. Woodall, Improper colourings of graphs, in:Graph Colourings, eds. R. Nelson and R.J. Wilson (Longman Scientific and Technical, Harlow, 1990) pp. 45–63.
Author information
Authors and Affiliations
Institut für Mathematik, Universität Mannheim, D-618131, Mannheim, Germany
Günther Nürnberger & Frank Zeilfelder
Center for Constructive Approximation, Department of Mathematics, Vanderbilt University, Nashville, TN, 37240, USA
Larry L. Schumaker
- Günther Nürnberger
You can also search for this author inPubMed Google Scholar
- Larry L. Schumaker
You can also search for this author inPubMed Google Scholar
- Frank Zeilfelder
You can also search for this author inPubMed Google Scholar
Rights and permissions
About this article
Cite this article
Nürnberger, G., Schumaker, L.L. & Zeilfelder, F. Lagrange Interpolation byC1 Cubic Splines on Triangulated Quadrangulations.Advances in Computational Mathematics21, 357–380 (2004). https://doi.org/10.1023/B:ACOM.0000032044.49282.8a
Share this article
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative