Multivariate refinable Hermite interpolant

Han, Bin; Yu, Thomas; Piper, Bruce

doi:10.1090/S0025-5718-03-01623-5

Multivariate refinable Hermite interpolant
HTML articles powered by AMS MathViewer

by Bin Han, Thomas P.-Y. Yu and Bruce Piper PDF

Math. Comp. 73 (2004), 1913-1935 Request permission

Abstract:

We introduce a general definition of refinable Hermite interpolants and investigate their general properties. We also study a notion of symmetry of these refinable interpolants. Results and ideas from the extensive theory of general refinement equations are applied to obtain results on refinable Hermite interpolants. The theory developed here is constructive and yields an easy-to-use construction method for multivariate refinable Hermite interpolants. Using this method, several new refinable Hermite interpolants with respect to different dilation matrices and symmetry groups are constructed and analyzed. Some of the Hermite interpolants constructed here are related to well-known spline interpolation schemes developed in the computer-aided geometric design community (e.g., the Powell-Sabin scheme). We make some of these connections precise. A spline connection allows us to determine critical Hölder regularity in a trivial way (as opposed to the case of general refinable functions, whose critical Hölder regularity exponents are often difficult to compute). While it is often mentioned in published articles that “refinable functions are important for subdivision surfaces in CAGD applications", it is rather unclear whether an arbitrary refinable function vector can be meaningfully applied to build free-form subdivision surfaces. The bivariate symmetric refinable Hermite interpolants constructed in this article, along with algorithmic developments elsewhere, give an application of vector refinability to subdivision surfaces. We briefly discuss several potential advantages offered by such Hermite subdivision surfaces.

References

Carl de Boor, A practical guide to splines, Applied Mathematical Sciences, vol. 27, Springer-Verlag, New York-Berlin, 1978. MR 507062, DOI 10.1007/978-1-4612-6333-3
George C. Donovan, Jeffrey S. Geronimo, Douglas P. Hardin, and Peter R. Massopust, Construction of orthogonal wavelets using fractal interpolation functions, SIAM J. Math. Anal. 27 (1996), no. 4, 1158–1192. MR 1393432, DOI 10.1137/S0036141093256526
S. Mallat, A theory for multiresolution signal decomposition: The wavelet representation, IEEE Trans. on Patt. Anal. and Mach. Intell. 11 (1989), no. 7, 674–693.
Yves Meyer, Wavelets and operators, Cambridge Studies in Advanced Mathematics, vol. 37, Cambridge University Press, Cambridge, 1992. Translated from the 1990 French original by D. H. Salinger. MR 1228209
G. Strang and V. Strela, Short wavelets and matrix dilation equations, IEEE Trans. on Signal Process. (1995), 108–115.
R. E. Barnhill and J. A. Gregory, Polynomial interpolation to boundary data on triangles, Math. Comp. 29 (1975), 726–735. MR 375735, DOI 10.1090/S0025-5718-1975-0375735-3
James V. Burke, Adrian S. Lewis, and Michael L. Overton, Two numerical methods for optimizing matrix stability, Linear Algebra Appl. 351/352 (2002), 117–145. Fourth special issue on linear systems and control. MR 1917476, DOI 10.1016/S0024-3795(02)00260-4
Carlos Cabrelli, Christopher Heil, and Ursula Molter, Accuracy of lattice translates of several multidimensional refinable functions, J. Approx. Theory 95 (1998), no. 1, 5–52. MR 1645975, DOI 10.1006/jath.1997.3211
E. Catmull and J. Clark, Recurssive generated B-spline surfaces on arbitrary topological meshes, Comp. Aid. Geom. Des. 10 (1978), no. 6, 350–355.
Alfred S. Cavaretta, Wolfgang Dahmen, and Charles A. Micchelli, Stationary subdivision, Mem. Amer. Math. Soc. 93 (1991), no. 453, vi+186. MR 1079033, DOI 10.1090/memo/0453
Di-Rong Chen, Rong-Qing Jia, and S. D. Riemenschneider, Convergence of vector subdivision schemes in Sobolev spaces, Appl. Comput. Harmon. Anal. 12 (2002), no. 1, 128–149. MR 1874918, DOI 10.1006/acha.2001.0363
C. de Boor, Personal Communication, 2001.
C. de Boor, Multivariate piecewise polynimials, Acta Numerica (1993), 65–109.
D. Doo and M. Sabin, Analysis of the behavoir of recursive division surfaces near extraordinary points, Comp. Aid. Geom. Des. 10 (1978), no. 6, 356–360.
Serge Dubuc and Jean-Louis Merrien, Dyadic Hermite interpolation on a rectangular mesh, Adv. Comput. Math. 10 (1999), no. 3-4, 343–365. MR 1692252, DOI 10.1023/A:1018943002601
Nira Dyn and David Levin, Analysis of Hermite-interpolatory subdivision schemes, Spline functions and the theory of wavelets (Montreal, PQ, 1996) CRM Proc. Lecture Notes, vol. 18, Amer. Math. Soc., Providence, RI, 1999, pp. 105–113. MR 1676239, DOI 10.1090/crmp/018/11
N. Dyn, D. Levin, and J. A. Gregory, A butterfly subdivision scheme for surface interpolation with tension control, ACM Trans. Graph. 9 (1990), no. 2.
N. Dyn and T. Lyche, Hermite subdivision scheme for the evaluation of the Powell-Sabin $12$-split element, Approximation Theory IX (C. Chui and L.L. Schmaker, eds.), 1999, pp. 1–6.
Gerald Farin, Triangular Bernstein-Bézier patches, Comput. Aided Geom. Design 3 (1986), no. 2, 83–127. MR 867116, DOI 10.1016/0167-8396(86)90016-6
Bin Han, Analysis and construction of optimal multivariate biorthogonal wavelets with compact support, SIAM J. Math. Anal. 31 (1999/00), no. 2, 274–304. MR 1740939, DOI 10.1137/S0036141098336418
Bin Han, Analysis and construction of optimal multivariate biorthogonal wavelets with compact support, SIAM J. Math. Anal. 31 (1999/00), no. 2, 274–304. MR 1740939, DOI 10.1137/S0036141098336418
Bin Han, Approximation properties and construction of Hermite interpolants and biorthogonal multiwavelets, J. Approx. Theory 110 (2001), no. 1, 18–53. MR 1826084, DOI 10.1006/jath.2000.3545
—, The initial functions in a cascade algorithm, Wavelet Analysis: Twenty Years’ Developments, Proceedings of International Conference on Computational Harmonic Analysis (D.X. Zhou, ed.), 2002, pp. 154–178.
—, Vector cascade algorithms and refinable function vectors in Sobolev spaces, Preprint, available at http://www.ualberta.ca/~bhan/publ.htm, July 2002.
—, Computing the smoothness exponent of a symmetric multivariate refinable function, SIAM J. Matrix Anal. and Appl. 24 (2003), no. 3, 693–714.
B. Han, M. Overton, and T. P.-Y. Yu, Design of Hermite subdivision schemes aided by spectral radius optimization, SIAM J. Sci. Comput. 25 (2003), no. 2, 643–656.
Rong-Qing Jia, Approximation properties of multivariate wavelets, Math. Comp. 67 (1998), no. 222, 647–665. MR 1451324, DOI 10.1090/S0025-5718-98-00925-9
R. Q. Jia and Q. T. Jiang, Spectral analysis of the transition operator and its applications to smoothness analysis of wavelets, SIAM J. Matrix Anal. and Appl. 24 (2003), no. 4, 1071–1109.
J. M. Lane and R. F. Risenfeld, A theoretical development for the computer generation and display of piecewise polynomial functions, IEEE Trans. on Patt. Anal. and Mach. Intell. 2 (1980), no. 1, 35–46.
J.-L. Merrien, A family of Hermite interpolants by bisection algorithms, Numer. Algorithms 2 (1992), no. 2, 187–200. MR 1165905, DOI 10.1007/BF02145385
Jean-Louis Merrien, Dyadic Hermite interpolants on a triangulation, Numer. Algorithms 7 (1994), no. 2-4, 391–410. MR 1283107, DOI 10.1007/BF02140692
M. J. D. Powell and M. A. Sabin, Piecewise quadratic approximations on triangles, ACM Trans. Math. Software 3 (1977), no. 4, 316–325. MR 483304, DOI 10.1145/355759.355761
Amos Ron, Smooth refinable functions provide good approximation orders, SIAM J. Math. Anal. 28 (1997), no. 3, 731–748. MR 1443617, DOI 10.1137/S0036141095282486
Nickolas S. Sapidis (ed.), Designing fair curves and surfaces, Geometric Design Publications, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1994. Shape quality in geometric modeling and computer-aided design. MR 1298891, DOI 10.1137/1.9781611971521
J. Warren and H. Weimer, Subdivision methods for geometric design: A constructive approach, Morgan Kaufmann, 2001.
T. P.-Y. Yu, Approximation order/smoothness tradeoff in Hermite subdivision schemes, Proc. SPIE, Wavelets: Applications in Signal and Image Processing IX (A. F. Laine, M. A. Unser, and A. Aldroubi, eds.), vol. 4478, 2001, pp. 117–128.
—, Hermite subdivision surfaces: Applications of vector refinability to free-form surfaces, In preparation, 2001.
Ding-Xuan Zhou, Multiple refinable Hermite interpolants, J. Approx. Theory 102 (2000), no. 1, 46–71. MR 1736045, DOI 10.1006/jath.1999.3376