Esquemas de subdivisión no lineales: 25 años de historia a través de 75 contribuciones: Non-linear subdivision schemes: 25 years of history through 75 contributions

Sergio Amat; Sonia Busquier; David Levin; Juan C. Trillo

doi:10.56754/0719-0646.2702.461

DOI:

https://doi.org/10.56754/0719-0646.2702.461

Abstract

Subdivision schemes are a very useful tool in computer graphics and geometric modelling, allowing for the generation of curves and smooth surfaces starting from discrete data. Even though linear subdivision schemes are used profusely, non-linear schemes offer more flexibility, allowing for the handling of data with irregularities and making the shape preservation easier. In addition, these schemes are useful to deal with subdivision on manifolds, to correct Gibbs oscillations around singularities, and, in general, to try to tackle problems where linear approaches do not provide satisfactory results. This article reviews 25 years of contributions related to the construction, analysis, and use, in different applications, of non-linear subdivision schemes.

Resumen

Los esquemas de subdivisión son una herramienta muy utilizada en gráficos por computadora y modelado geométrico, permitiendo la generación de curvas y superficies suaves a partir de datos discretos. Aunque los esquemas de subdivisión lineales son muy utilizados, los esquemas no lineales ofrecen mayor flexibilidad, permitiendo el manejo de datos con irregularidades y facilitando la preservación de formas. Además, estos esquemas son útiles para abordar subdivisión en variedades, corregir las oscilaciones de Gibbs alrededor de singularidades y en general intentar abordar problemas donde los enfoques lineales no aportan resultados satisfactorios. Este artículo revisa 25 años de contribuciones relacionadas con la construcción, el análisis y el uso, en diversas aplicaciones, de esquemas de subdivisión no lineales.

Keywords

Non-linear subdivision , geometric approximation , surface representation , multiresolution schemes , computer graphics applications , geometric processing

Mathematics Subject Classification:

65D05 , 65D17 , 68U05 , 68U07

Sergio Amat Departamento de Matemática Aplicada y Estadística, Universidad Politécnica de Cartagena, España. https://orcid.org/0000-0002-9954-5240
Sonia Busquier Departamento de Matemática Aplicada y Estadística, Universidad Politécnica de Cartagena, España. https://orcid.org/0000-0003-0910-2030
David Levin School of Mathematical Sciences. Tel-Aviv University, Tel-Aviv, Israel. https://orcid.org/0000-0003-4533-500X
Juan C. Trillo Departamento de Matemática Aplicada y Estadística, Universidad Politécnica de Cartagena, España. https://orcid.org/0000-0001-5566-8663

Pages: 461–504
Date Published: 2025-10-21
Vol. 27 No. 2 (2025): Spanish Edition (40th Anniversary)

S. Amat, A. Choutri, J. Ruiz, y S. Zouaoui, “On a nonlinear 4-point ternary and non-interpolatory subdivision scheme eliminating the Gibbs phenomenon,” Appl. Math. Comput., vol. 320, pp. 16–26, 2018, doi: 10.1016/j.amc.2017.08.055.

S. Amat, K. Dadourian, y J. Liandrat, “Analysis of a class of nonlinear subdivision schemes and associated multiresolution transforms,” Adv. Comput. Math., vol. 34, no. 3, pp. 253–277, 2011, doi: 10.1007/s10444-010-9151-6.

S. Amat, K. Dadourian, J. Liandrat, J. Ruiz, y J. C. Trillo, “A family of stable nonlinear nonseparable multiresolution schemes in 2D,” J. Comput. Appl. Math., vol. 234, no. 4, pp. 1277–1290, 2010, doi: 10.1016/j.cam.2009.10.003.

S. Amat y J. Liandrat, “On a nonlinear 4-point quaternary approximating subdivision scheme eliminating the Gibbs phenomenon,” SeMA J., vol. 62, pp. 15–25, 2013, doi: 10.1007/s40324-013-0006-1.

S. Amat, F. Aràndiga, A. Cohen, R. Donat, G. Garcia, y M. von Oehsen, “Data compression with ENO schemes: a case study,” Appl. Comput. Harmon. Anal., vol. 11, no. 2, pp. 273–288, 2001, doi: 10.1006/acha.2001.0356.

S. Amat, F. Aràndiga, A. Cohen, y R. Donat, “Tensor product multiresolution analysis with ENO schemes: a case study,” Signal Processing, vol. 82, no. 4, pp. 587–608, 2002, doi: 10.1016/S0165-1684(01)00206-7.

S. Amat, S. Busquier, y J. C. Trillo, “On multiresolution schemes using a stencil selection procedure: applications to ENO schemes,” Numer. Algorithms, vol. 44, no. 1, pp. 45–68, 2007, doi: 10.1007/s11075-007-9083-5.

S. Amat, R. Donat, J. Liandrat, y J. C. Trillo, “Analysis of a new nonlinear subdivision scheme. Applications in image processing,” Found. Comput. Math., vol. 6, no. 2, pp. 193–225, 2006, doi: 10.1007/s10208-004-0122-5.

S. Amat, J. Liandrat, J. Ruiz, y J. C. Trillo, “On a nonlinear cell-average multiresolution scheme for image compression,” SeMA J., no. 60, pp. 75–92, 2012, doi: 10.1007/bf03391711.

S. Amat, J. Ruiz, J. C. Trillo, y D. F. Yáñez, “On a stable family of four-point nonlinear subdivision schemes eliminating the Gibbs phenomenon,” J. Comput. Appl. Math., vol. 354, pp. 310–325, 2019, doi: 10.1016/j.cam.2018.04.058.

S. Amat, J. Ruiz, J. C. Trillo, y D. F. Yáñez, “On a family of non-oscillatory subdivision schemes having regularity C^r with r > 1,” Numer. Algorithms, vol. 85, no. 2, pp. 543–569, 2020, doi: 10.1007/s11075-019-00826-3.

F. Aràndiga y R. Donat, “Nonlinear multiscale decompositions: the approach of A. Harten,” Numer. Algorithms, vol. 23, no. 2–3, pp. 175–216, 2000.

F. Aràndiga, R. Donat, y M. Santagüeda, “Weighted-power_p nonlinear subdivision schemes,” en Curves and Surfaces, Berlin: Springer, 2012, pp. 109–129, doi: 10.1007/978-3-642-27413-8_7.

M. Aslam, “(2n–1)-point nonlinear ternary interpolating subdivision schemes,” Int. J. Appl. Math., vol. 31, no. 3, pp. 413–425, 2018, doi: 10.12732/ijam.v31i3.9.

M. Aslam, “A family of 5-point nonlinear ternary interpolating subdivision schemes with C² smoothness,” Math. Comput. Appl., vol. 23, no. 2, 2018, Art. ID 18, doi: 10.3390/mca23020018.

R. Bürger, R. Ruiz, K. Schneider, y M. Sepúlveda, “Fully adaptive multiresolution schemes for strongly degenerate parabolic equations in one space dimension,” M2AN Math. Model. Numer. Anal., vol. 42, no. 4, pp. 535–563, 2008, doi: 10.1051/m2an:2008016.

P. Chalmoianský y B. Jüttler, “A non-linear circle-preserving subdivision scheme,” Adv. Comput. Math., vol. 27, no. 4, pp. 375–400, 2007, doi: 10.1007/s10444-005-9011-y.

F. Cirak y Q. Long, “Subdivision shells with exact boundary control and non-manifold geometry,” Internat. J. Numer. Methods Engrg., vol. 88, no. 9, pp. 897–923, 2011, doi: 10.1002/nme.3206.

A. Cohen, N. Dyn, y B. Matei, “Quasilinear subdivision schemes with applications to ENO interpolation,” Appl. Comput. Harmon. Anal., vol. 15, no. 2, pp. 89–116, 2003, doi: 10.1016/S1063-5203(03)00061-7.

F. Coquel, M. Postel, N. Poussineau, y Q. H. Tran, “Multiresolution technique and explicit-implicit scheme for multicomponent flows,” J. Numer. Math., vol. 14, no. 3, pp. 187–216, 2006, doi: 10.1163/156939506778658294.

P. Costantini y C. Manni, “On constrained nonlinear Hermite subdivision,” Constr. Approx., vol. 28, no. 3, pp. 291–331, 2008, doi: 10.1007/s00365-007-9001-z.

M. Cotronei, C. Moosmüller, T. Sauer, y N. Sissouno, “Hermite multiwavelets for manifold-valued data,” Adv. Comput. Math., vol. 49, no. 3, 2023, Art. ID 40.

C. de Boor, “Preserving geometric features in nonlinear subdivision,” SIAM J. Numer. Anal., vol. 34, no. 5, pp. 1605–1622, 1997, doi: 10.1137/0733060.

R. A. DeVore y A. Kunoth, Eds., Multiscale, nonlinear and adaptive approximation. Springer-Verlag, Berlin, 2009, doi: 10.1007/978-3-642-03413-8.

R. Donat, S. López-Ureña, y M. Santagüeda, “A family of non-oscillatory 6-point interpolatory subdivision schemes,” Adv. Comput. Math., vol. 43, no. 4, pp. 849–883, 2017, doi: 10.1007/s10444-016-9509-5.

T. Duchamp, G. Xie, y T. Y. Yu, “Single basepoint subdivision schemes for manifold-valued data: time-symmetry without space-symmetry,” Found. Comput. Math., vol. 13, no. 5, pp. 693–728, 2013, doi: 10.1007/s10208-013-9144-1.

T. Duchamp, G. Xie, y T. Y. Yu, “A necessary and sufficient proximity condition for smoothness equivalence of nonlinear subdivision schemes,” Found. Comput. Math., vol. 16, no. 5, pp. 1069–1114, 2016, doi: 10.1007/s10208-015-9268-6.

N. Dyn, “Three families of nonlinear subdivision schemes,” en Topics in multivariate approximation and interpolation, ser. Stud. Comput. Math. Elsevier B.V., Amsterdam, 2006, vol. 12, pp. 23–38, doi: 10.1016/S1570-579X(06)80003-0.

N. Dyn, “Linear and nonlinear subdivision schemes in geometric modeling,” en Foundations of computational mathematics, Hong Kong 2008, ser. London Math. Soc. Lecture Note Ser. Cambridge Univ. Press, Cambridge, 2009, vol. 363, pp. 68–92.

N. Dyn, P. Grohs, y J. Wallner, “Approximation order of interpolatory nonlinear subdivision schemes,” J. Comput. Appl. Math., vol. 233, no. 7, pp. 1697–1703, 2010.

N. Dyn, D. Levin, y M. S. Floater, “Nonlinear subdivision schemes and their applications,” en Geometric Modeling and Computing. Springer, 2002, pp. 1–24.

N. Dyn y P. Oswald, “Univariate subdivision and multi-scale transforms: the nonlinear case,” en Multiscale, nonlinear and adaptive approximation. Springer, Berlin, 2009, pp. 203–247, doi: 10.1007/978-3-642-03413-8_7.

O. Ebner, “Convergence of refinement schemes on metric spaces,” Proc. Amer. Math. Soc., vol. 141, no. 2, pp. 677–686, 2013, doi: 10.1090/S0002-9939-2012-11331-0.

T. Ewald, U. Reif, y M. Sabin, “Hölder regularity of geometric subdivision schemes,” Constr. Approx., vol. 42, no. 3, pp. 425–458, 2015, doi: 10.1007/s00365-015-9305-3.

M. S. Floater y C. A. Micchelli, “Nonlinear stationary subdivision,” en Approximation Theory. CRC Press, Taylor & Francis, 1998, p. 209, doi: 10.1201/9781003064732-14.

R. Goldman, E. Vouga, y S. Schaefer, “On the smoothness of real-valued functions generated by subdivision schemes using nonlinear binary averaging,” Comput. Aided Geom. Design, vol. 26, no. 2, pp. 231–242, 2009, doi: 10.1016/j.cagd.2008.04.004.

P. Grohs, “Smoothness analysis of subdivision schemes on regular grids by proximity,” SIAM J. Numer. Anal., vol. 46, no. 4, pp. 2169–2182, 2008, doi: 10.1137/060669759.

P. Grohs, “Smoothness equivalence properties of univariate subdivision schemes and their projection analogues,” Numer. Math., vol. 113, no. 2, pp. 163–180, 2009, doi: 10.1007/s00211-009-0231-9.

P. Grohs, “Approximation order from stability for nonlinear subdivision schemes,” J. Approx. Theory, vol. 162, no. 5, pp. 1085–1094, 2010, doi: 10.1016/j.jat.2009.12.003.

P. Grohs, “A general proximity analysis of nonlinear subdivision schemes,” SIAM J. Math. Anal., vol. 42, no. 2, pp. 729–750, 2010, doi: 10.1137/09075963X.

P. Grohs y J. Wallner, “Log-exponential analogues of univariate subdivision schemes in Lie groups and their smoothness properties,” en Approximation theory XII: San Antonio 2007, ser. Mod. Methods Math. Nashboro Press, Brentwood, TN, 2008, pp. 181–190.

P. Grohs y J. Wallner, “Interpolatory wavelets for manifold-valued data,” Appl. Comput. Harmon. Anal., vol. 27, no. 3, pp. 325–333, 2009, doi: 10.1016/j.acha.2009.05.005.

A. Guessab, M. Moncayo, y G. Schmeisser, “A class of nonlinear four-point subdivision schemes,” Adv. Comput. Math., vol. 37, no. 2, pp. 151–190, 2012, doi: 10.1007/s10444-011-9199-y.

S. Harizanov y P. Oswald, “Stability of nonlinear subdivision and multiscale transforms,” Constr. Approx., vol. 31, no. 3, pp. 359–393, 2010, doi: 10.1007/s00365-010-9082-y.

A. Harten, “Discrete multi-resolution analysis and generalized wavelets,” 1993, vol. 12, no. 1–3, pp. 153–192, doi: 10.1016/0168-9274(93)90117-A.

A. Harten, “Multiresolution representation of data: a general framework,” SIAM J. Numer. Anal., vol. 33, no. 3, pp. 1205–1256, 1996, doi: 10.1137/0733060.

V. Hernández-Mederos, J. C. Estrada-Sarlabous, S. R. Morales, e I. Ivissimitzis, “Curve subdivision with arc-length control,” Computing, vol. 86, no. 2–3, pp. 151–169, 2009, doi: 10.1007/s00607-009-0068-1.

S. Hüning y J. Wallner, “Convergence analysis of subdivision processes on the sphere,” IMA J. Numer. Anal., vol. 42, no. 1, pp. 698–711, 2022, doi: 10.1093/imanum/draa086.

M. K. Jena, “A Hermite interpolatory subdivision scheme constructed from quadratic rational Bernstein–Bezier spline,” Math. Comput. Simulation, vol. 187, pp. 433–448, 2021.

L. Kobbelt, “Interpolatory subdivision on open quadrilateral nets with arbitrary topology,” Comput. Graph. Forum, vol. 15, no. 3, pp. 409–420, 1996, doi: 10.1111/1467-8659.1530409.

Z. Kui, J. Baccou, y J. Liandrat, “On the coupling of decimation operator with subdivision schemes for multi-scale analysis,” en Mathematical methods for curves and surfaces, ser. Lecture Notes in Comput. Sci. Springer, Cham, 2017, vol. 10521, pp. 162–185, doi: 10.1007/978-3-319-67885-6_9.

J.-a. Lian, “A new four point circular-invariant corner-cutting subdivision for curve design,” Appl. Appl. Math., vol. 7, no. 1, pp. 464–486, 2012.

J.-a. Lian, Y. Wang, y Y. Yang, “Circular nonlinear subdivision schemes for curve design,” Appl. Appl. Math., vol. 4, no. 1, pp. 1–12, 2009.

S. Marschner, “Manifold-based methods in geometric modeling,” ACM Trans. Graph., vol. 17, no. 2, pp. 149–160, 1998, doi: 10.1145/274279.274282.

B. Matei, S. Meignen, y A. Zakharova, “Smoothness of non-linear and non-separable subdivision schemes,” Asymptot. Anal., vol. 74, no. 3–4, pp. 229–247, 2011.

C. Moosmüller, “C¹ analysis of Hermite subdivision schemes on manifolds,” SIAM J. Numer. Anal., vol. 54, no. 5, pp. 3003–3031, 2016, doi: 10.1137/15M1033459.

E. Nava-Yazdani y T. P.-Y. Yu, “On Donoho’s log-exp subdivision scheme: choice of retraction and time-symmetry,” Multiscale Model. Simul., vol. 9, no. 4, pp. 1801–1828, 2011, doi: 10.1137/100804838.

P. Oswald, “Smoothness of nonlinear median-interpolation subdivision,” Adv. Comput. Math., vol. 20, no. 4, pp. 401–423, 2004, doi: 10.1023/A:1027315032100.

P. Oswald, “Nonlinear multi-scale transforms: L_p theory,” J. Franklin Inst., vol. 349, no. 5, pp. 1619–1636, 2012, doi: 10.1016/j.jfranklin.2011.06.006.

U. Reif y A. Weinmann, “Clothoid fitting and geometric Hermite subdivision,” Adv. Comput. Math., vol. 47, no. 4, 2021, Art. ID 50, doi: 10.1007/s10444-021-09876-5.

M. Sabin, “Two open questions relating to subdivision,” Computing, vol. 86, no. 2–3, pp. 213–217, 2009, doi: 10.1007/s00607-009-0059-2.

S. Schaefer, E. Vouga, y R. Goldman, “Nonlinear subdivision through nonlinear averaging,” Comput. Aided Geom. Design, vol. 25, no. 3, pp. 162–180, 2008, doi: 10.1016/j.cagd.2007.07.003.

J. Wallner, “Smoothness analysis of subdivision schemes by proximity,” Constr. Approx., vol. 24, no. 3, pp. 289–318, 2006, doi: 10.1007/s00365-006-0638-3.

A. Weinmann, “Nonlinear subdivision schemes on irregular meshes,” Constr. Approx., vol. 31, no. 3, pp. 395–415, 2010, doi: 10.1007/s00365-009-9063-1.

A. Weinmann, “Subdivision schemes with general dilation in the geometric and nonlinear setting,” J. Approx. Theory, vol. 164, no. 1, pp. 105–137, 2012, doi: 10.1016/j.jat.2011.09.005.

G. Xie y T. P.-Y. Yu, “Smoothness equivalence properties of manifold-valued data subdivision schemes based on the projection approach,” SIAM J. Numer. Anal., vol. 45, no. 3, pp. 1200–1225, 2007, doi: 10.1137/060652944.

G. Xie y T. P.-Y. Yu, “Smoothness equivalence properties of general manifold-valued data subdivision schemes,” Multiscale Model. Simul., vol. 7, no. 3, pp. 1073–1100, 2008, doi: 10.1137/080718723.

G. Xie y T. P.-Y. Yu, “Approximation order equivalence properties of manifold-valued data subdivision schemes,” IMA J. Numer. Anal., vol. 32, no. 2, pp. 687–700, 2012, doi: 10.1093/imanum/drq046.

G. Xie y T. P.-Y. Yu, “Invariance property of proximity conditions in nonlinear subdivision,” J. Approx. Theory, vol. 164, no. 8, pp. 1097–1110, 2012, doi: 10.1016/j.jat.2012.05.001.

X. Yang, “Normal based subdivision scheme for curve design,” Comput. Aided Geom. Design, vol. 23, no. 3, pp. 243–260, 2006, doi: 10.1016/j.cagd.2005.10.001.

X. Yang, “Point-normal subdivision curves and surfaces,” Comput. Aided Geom. Design, vol. 104, 2023, Art. ID 102207, doi: 10.1016/j.cagd.2023.102207.

T. P.-Y. Yu, “How data dependent is a nonlinear subdivision scheme? A case study based on convexity preserving subdivision,” SIAM J. Numer. Anal., vol. 44, no. 3, pp. 936–948, 2006, doi: 10.1137/050628751.

Z. Zhang, H. Zheng, J. Zhou, y L. Pan, “A nonlinear generalized subdivision scheme of arbitrary degree with a tension parameter,” Adv. Difference Equ., 2020, Art. ID 655, doi: 10.1186/s13662-020-03118-6.