Proximity Analysis for Nonlinear Subdivision Schemes

17 concepts4 papers1 proposal

Subdivision schemes are a foundational tool in computational mathematics and computer graphics for generating smooth curves and surfaces. By starting with a coarse grid of discrete data points and repeatedly applying refinement rules, these schemes generate increasingly dense sequences of points that converge to a continuous limit.

In a standard Euclidean space, these refinement rules are linear—typically simple weighted averages of neighboring points. Linear schemes are exceptionally well-understood: we can easily predict their smoothness ($C^1, C^2$, etc.) and their approximation order using Fourier analysis and polynomial generation properties.

However, real-world data often lives on curved surfaces or geometric manifolds rather than flat Euclidean spaces. For example, tracking the positions and orientations of a rigid body involves data on the manifold of 3D rotations ($SO(3)$). If you take a linear average of two rotation matrices, the result is generally no longer a valid rotation matrix. To handle such data, researchers must design nonlinear subdivision schemes that respect the underlying geometry (e.g., by computing averages along geodesics).

Predicting the behavior of these nonlinear schemes from scratch is notoriously difficult because the standard linear tools no longer apply. Proximity analysis solves this dilemma through a powerful paradigm: instead of analyzing a nonlinear scheme directly, we can bound how much it deviates from a well-understood linear counterpart. If the nonlinear scheme is sufficiently "close" to the linear scheme, it inherits the linear scheme's convergence, smoothness, and accuracy guarantees.


The Core Intuition: Local Flatness

To understand why proximity analysis works, imagine zooming in on a smooth surface like a globe. Up close, the curvature becomes imperceptible, and the surface looks increasingly flat.

A well-designed nonlinear subdivision scheme mimics this property. As the subdivision process progresses, the generated data points become closer and closer together. On this microscopic scale, the curved manifold behaves almost exactly like a flat Euclidean space. Therefore, the nonlinear refinement rule should behave almost exactly like a linear refinement rule.

Proximity analysis formalizes this intuition using proximity inequalities. Let $S$ represent a linear subdivision operator and $T$ represent a nonlinear subdivision operator. We want to evaluate how much the output of the nonlinear step deviates from the linear step, denoted as $\|T(x) - S(x)\|$.

As shown by Nira Dyn et al., these inequalities bound the difference between the outputs of the two schemes as a function of the distances between the input data points:

$$\|T(x) - S(x)\| \le C \cdot \Delta(x)^k$$

where $\Delta(x)$ measures the max distance between adjacent input points, $C$ is a constant, and $k$ is an exponent dictating how fast the error decays. Because the input points get closer together with each step of subdivision ($\Delta(x) \to 0$), the nonlinear scheme rapidly converges toward its linear counterpart. If this deviation decays fast enough, the perturbations introduced by the nonlinearity are too small to destroy the geometric properties of the limit curve.


Transferring Smoothness

The primary historical obstacle in nonlinear subdivision was proving that a scheme would yield a smooth ($C^1$ or higher) limit curve without artifacts.

In Smoothness Analysis of Subdivision Schemes on Regular Grids by Proximity, Philipp Grohs established a rigorous framework showing that proximity conditions act as a bridge for smoothness equivalence. If a linear scheme is known to produce $C^1$ smooth curves, and a nonlinear scheme satisfies a strict proximity bound relative to it, the nonlinear scheme is guaranteed to produce $C^1$ smooth curves as well.

This framework was later expanded by Philipp Grohs in A General Proximity Analysis of Nonlinear Subdivision Schemes. By mapping the polynomial generation properties of linear schemes directly to the proximity conditions required for manifold analysis, the author proved that Riemannian analogues of linear schemes can achieve arbitrarily high smoothness ($C^r$), particularly when operating on non-positively curved spaces like Cartan-Hadamard manifolds.


Transferring Approximation Order

Smoothness tells us that a curve is visually continuous and lacks sharp kinks, but it does not tell us how accurately the subdivision scheme can approximate an underlying target function. This accuracy is measured by the approximation order. If a scheme has an approximation order of $r+1$, it means that as the initial grid spacing $h$ tends to zero, the error between the subdivision limit and the true function shrinks at a rate proportional to $h^{r+1}$.

Linear schemes achieve high approximation orders by exactly reproducing polynomials up to degree $r$. Nonlinear schemes cannot reproduce polynomials globally due to the constraints of the manifold.

To resolve this, Nira Dyn et al. focused on interpolatory nonlinear schemes. The authors demonstrated that the degree to which a nonlinear scheme deviates from a linear baseline determines whether it preserves or degrades accuracy. By satisfying precise proximity inequalities, the nonlinear scheme can inherit the exact same high-order accuracy ($r+1$) of a $C^r$ interpolatory linear scheme. This provides a predictable recipe for designing highly accurate geometric algorithms.


Beyond Curves: Stability in Multiscale Decompositions

The utility of proximity analysis extends beyond just generating smooth curves; it also provides a foundation for signal processing on manifolds, such as wavelets and multiscale decompositions.

When decomposing a signal into different frequency bands (coarse overviews plus fine details), a critical requirement is stability: a small perturbation or noise in the wavelet coefficients should not cause wild, unpredictable distortions in the reconstructed signal. In Euclidean space, stability is guaranteed by the linearity of the operators. On manifolds, the lack of linearity threatens to amplify errors across scales.

In Definability and stability of multiscale decompositions for manifold-valued data, Johannes Wallner et al. applied proximity analysis to this problem. They demonstrated that specific nonlinear schemes (such as midpoint-interpolating schemes) behave similarly enough to standard linear rules under small perturbations to preserve stability. By bounding the nonlinear deviations at each scale, the authors proved that the robust stability guarantees of Euclidean multiscale frameworks can be successfully transferred to curved, manifold-valued data.

Key Foundational Work

Approximation order of interpolatory nonlinear subdivision schemes (2010) — contributed 10 concept elements to this direction.
Smoothness Analysis of Subdivision Schemes on Regular Grids by Proximity (2008) — contributed 3 concept elements to this direction.
A General Proximity Analysis of Nonlinear Subdivision Schemes (2010) — contributed 3 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_transfer_of_approximation_order_05a9ae97,
  title = {transfer of approximation order},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/transfer-of-approximation-order/rdr_05a9ae9790174593b5970418aeda32bd},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_transfer_of_approximation_order_05a9ae97_v1,
  title = {transfer of approximation order},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/transfer-of-approximation-order/rdr_05a9ae9790174593b5970418aeda32bd/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake