Hierarchical Radial-Basis-Function Interpolation¶

Interpolate scattered spatial data by recursively partitioning it into overlapping local RBF systems and blending their solutions through a spatial tree.

Version: v3 · 2026-09-19 · History
Domain-specific #: 2003
Domain group: Applied Sciences & Engineering
Origin domain: Computer Science & Software Engineering
Subdomains: Computer Graphics, Geometric Modeling → Computer Science & Software Engineering
Aliases: Adaptive hierarchical RBF interpolation

Core Idea¶

Hierarchical radial-basis-function interpolation is an adaptive scattered-data method that replaces one large global RBF system with a recursive collection of smaller, overlapping local systems. In the precise construction used here, the hierarchy is a balanced binary spatial tree and its evaluation rule is a bottom-up partition-of-unity blend.

Start with pairwise-distinct sites

\[ P=\{p_i\}_{i=1}^{N}\subset\Omega\subset\mathbb R^d \]

and scalar values \(h_i\). Recursively divide the spatial domain along a coordinate direction so that the child regions have nearly balanced point counts. Enlarge their interface enough to create overlap, and continue until each leaf contains no more than a chosen capacity \(T_{leaf}\). For every leaf \(\ell\), solve an RBF interpolant.

How would you explain it like I'm…

Patchwork Smooth Hill

Say you know how tall the ground is at a few spots and want to draw a smooth hill through them. Hierarchical Radial-Basis-Function Interpolation cuts the map in half again and again into small, slightly overlapping pieces. Each piece draws its own little hill. Where pieces overlap, their hills are gently mixed so the whole thing looks like one smooth hill.

Split, Solve, and Blend

Suppose you know a value, like temperature, at scattered points and want a smooth surface through all of them. Doing one giant calculation for every point is slow. Hierarchical radial-basis-function interpolation keeps splitting the area in half, so each half has about the same number of points, and makes the halves overlap a little. Once a piece is small enough, it gets its own smooth fit made from round 'bump' shapes. The pieces are then blended back together step by step, with smooth weights in the overlaps, so the final surface still passes through every point.

Tree-Blended Local RBF Fits

A radial basis function (RBF) interpolant builds a smooth function by adding up kernels that depend only on distance from each data site, chosen so the function hits every data value exactly. With many points, one global system becomes huge. This method instead recursively splits the domain along coordinate directions into a balanced binary tree, with overlapping children, until each leaf holds only a few points. Each leaf solves its own small RBF system, including any required polynomial term. Moving up the tree, each parent blends its two children using smooth weights that are normalized to add to one. Where both children match a data value, the blend matches it too. This is a specific tree-and-blend construction, not every method that is called 'multilevel RBF'.

Hierarchical Radial-Basis-Function Interpolation interpolates scattered data: distinct sites p_i in R^d with values h_i. The domain is recursively bisected along coordinate directions into a balanced binary spatial tree. Each interface is widened to create overlap, and splitting continues until each leaf has at most T_leaf points. Each leaf solves a local RBF interpolant s_ℓ(x) = Σ λ_j φ(‖x − p_j‖) + q_ℓ(x). If φ is only conditionally positive definite, the polynomial q_ℓ and its moment constraints must be included even though the system is small. At each internal node, the child functions are combined as (Λ_L s_L + Λ_R s_R)/(Λ_L + Λ_R). The weights are nonnegative, smooth, and vanish outside each child's support, so normalization gives a partition of unity. Where all active children interpolate a shared sample, the blend does too, and smooth fits combined with smooth weights give continuity. The tree is therefore both the computation schedule and the structure of the final interpolant.

Scope of Application¶

The home habitat is large scattered spatial interpolation in computer graphics, terrain modeling, geometric modeling, and surface reconstruction. The method is most natural when a dense global RBF solve is undesirable, the data have useful spatial locality, and a continuous field must be queried at many off-sample positions.

Within that habitat it supports height-field reconstruction from terrain samples, implicit or parametric surface fitting, and related scientific or medical geometry in which local RBF patches can be organized spatially.

Clarity¶

A compact recognition test is: where are the interpolation constraints solved, and how do their functions become one answer? If all centers enter one coefficient solve, the method is global RBF interpolation. If local systems lie on an unstructured flat cover, it is generic RBF-PU. If level \(k+1\) fits the residual left by level \(k\), it is a multistep or multilevel correction method.

Manages Complexity¶

A dense direct factorization of one \(N\)-center RBF interpolation matrix has the familiar \(O(N^3)\) arithmetic and \(O(N^2)\) storage profile. If a balanced hierarchy has \(L\approx N/T_{leaf}\) leaves and local size is bounded by \(T_{leaf}\), independent leaf factorizations require

Abstract Reasoning¶

Reason about the method by separating local fidelity, interface compatibility, and hierarchical transport.

First, verify each leaf as an RBF interpolation problem: kernel assumptions, polynomial augmentation, non-singularity conditions, and sample residuals. Second, verify the interface: active weights must be nonnegative where required, have nonzero total weight, cover the transition region, and possess the smoothness claimed for the global field.

Knowledge Transfer¶

B — bounded domain transfer. The complete mechanism transfers reliably among neighboring scattered-geometry practices: terrain height fields, implicit surface reconstruction, scientific visualization, and geometric modeling. Across these cases the roles remain literal—spatial samples, radial kernels, overlapping bounded local systems, a region tree, and a blended field—even though dimensions, kernels, and the interpretation of a level set may change.

Relationships to Other Abstractions¶

Current abstraction Hierarchical Radial-Basis-Function Interpolation Domain-specific

Parents (2) — outgoing typed relations

Hierarchical Radial-Basis-Function Interpolation includes Hierarchy Prime

The method strictly instantiates Decomposition: one global dense interpolation problem is divided into bounded local systems and their results are recombined.
Hierarchical Radial-Basis-Function Interpolation is a decomposition of Decomposition Prime

The method strictly instantiates Decomposition: one global dense interpolation problem is divided into bounded local systems and their results are recombined.

Hierarchy paths (5) — routes to 5 parentless roots

Hierarchical Radial-Basis-Function Interpolation → includes Hierarchy → is a kind of Network

Show alternative paths (4)

Neighborhood in Abstraction Space¶

Hierarchical Radial-Basis-Function Interpolation sits in a sparse region of the domain-specific corpus (77^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Unclustered & Miscellaneous (2769 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-25