betaFeedback

WorksMathematics

Data-dependent Compact Multinode Shepard Method

Abstract

We introduce a data-dependent compact multinode Shepard method for the approximation of scattered multivariate data. The proposed approach extends the compact multinode Shepard operator by incorporating nonlinear, data-dependent weights inspired by the weighted essentially non-oscillatory (WENO) methodology while preserving the partition of unity structure and the locality of the approximation. The construction is based on compactly supported multinode weight functions associated with local polynomial interpolants defined on unisolvent stencils. A smoothness indicator is employed to adapt the contribution of each stencil according to the local regularity of the underlying function, thereby reducing spurious oscillations near discontinuities while retaining the optimal approximation order in smooth regions. We establish the theoretical approximation properties of the proposed operator: it achieves the order of accuracy of its linear counterpart for sufficiently smooth functions and, under an explicit indicator-separation hypothesis, the same order is retained at every covered evaluation point near a jump discontinuity. Numerical experiments for local degrees up to four illustrate the performance of the method on both smooth and non-smooth data, on scattered as well as on gridded nodes.

Introduction

Scattered data approximation deals with the problem of reconstructing an unknown function from values prescribed at irregularly distributed data sites. The absence of an underlying grid or mesh makes this setting particularly attractive in applications where data are collected at irregularly distributed locations and no natural mesh is available. Among the several techniques developed for this purpose, Shepard-type methods have retained considerable interest because of their simple structure, their meshfree character, and the ease with which they can be applied to arbitrarily scattered data. The classical Shepard method [1] constructs the approximant as a normalized weighted average of the data values, using inverse powers of the distances from the evaluation point. Its partition of unity structure immediately provides stability properties, and the singularity of the weights at the nodes makes it interpolatory. However, the fact that only constants are reproduced limits the approximation order that can be achieved.

A considerable part of the subsequent development of Shepard-type methods has therefore been devoted to improving the accuracy and the locality of the original construction while preserving its basic simplicity. Compactly supported weights were introduced to restrict the influence of distant data sites and to obtain local approximations [2]. A different direction, originating from the triangular Shepard construction, consists in replacing the individual data values by polynomial interpolants based on small subsets of the nodes. This idea leads to the multinode Shepard method [3, 4, 5], in which local polynomial interpolants are blended through a partition of unity generated by products of inverse distances. By increasing the degree of the local polynomials, the method retains the interpolatory character of the classical Shepard construction while achieving higher approximation orders on sufficiently smooth functions. More recently, the same multinode principle has been combined with compactly supported weights in the interpolation of scattered data on the torus [6], providing a local version of the multinode construction.

The use of higher-degree local interpolants, however, also makes the quality of the approximation increasingly dependent on the regularity of the data contained in each stencil. When the underlying function is only piecewise smooth, a stencil may contain data belonging to different smooth branches. The corresponding polynomial interpolant can then be a poor local representation of either branch and may produce pronounced oscillatory effects in a neighborhood of the discontinuity. This difficulty is not specific to Shepard approximation and is closely related to the general problem of approximating piecewise smooth functions from scattered data; see, for example, [7, 8, 9]. In the linear multinode Shepard construction all the stencils whose supports contain the evaluation point (the active stencils, § 3) contribute according to geometrically determined weights, independently of the regularity of the data from which their local interpolants are built. It is therefore natural to ask whether the partition of unity mechanism can be made sensitive to the local behavior of the data, so that contributions associated with nonsmooth configurations are reduced without affecting the approximation in smooth regions.

This is the point of view adopted in the present paper. Our construction is inspired by the weighted essentially non-oscillatory (WENO) methodology [10], whose basic principle is to assign nonlinear weights according to suitable measures of local smoothness. WENO-type modifications of partition of unity approximation have already been considered for B-spline bases [11] (see also [12]), while a data-dependent version of the classical Shepard method has been developed in [13]. Related nonlinear approaches have also been proposed for radial basis function (RBF) partition of unity approximation [14] and moving least squares approximation [15]. Here we combine this nonlinear weighting principle with the compact multinode Shepard construction. Each local polynomial interpolant is associated with a smoothness indicator, and the corresponding compact multinode weight is modified according to the value of this indicator before the partition of unity is renormalized. In the construction considered in this paper, the indicator is obtained from the residuals of the local polynomial at data sites lying outside the interpolation stencil. Since these values are already part of the available scattered data, the indicator does not require additional function evaluations.

The resulting operator remains local and interpolatory and preserves the partition of unity structure of the underlying compact multinode method. Its nonlinear character is relevant only in the relative weight assigned to the active local interpolants. This observation is particularly useful in smooth regions: once the local interpolants have the expected approximation accuracy, any convex combination of them inherits the same order. We show, in fact, that under uniform locality and stability assumptions the data-dependent operator retains the order O(hd+1)O(h^{d+1}) of the multinode construction for sufficiently smooth functions, where hh is the fill distance of the node set and dd the degree of the local polynomial interpolants, independently of the nonlinear exponent. For piecewise smooth functions separated by a jump discontinuity, the analysis is necessarily more delicate. We identify explicit conditions under which the smooth and contaminated contributions are separated by the indicator and prove that the same approximation order is recovered at evaluation points satisfying these conditions. At the same time, we show by an explicit configuration that the residual indicator does not detect every stencil crossing a discontinuity. The convergence analysis requires that at least one suitable active stencil lying on one side of the discontinuity has a small smoothness indicator, while all active stencils crossing the discontinuity have indicators uniformly bounded away from zero. We refer to this requirement as indicator separation and impose it explicitly, since it is not guaranteed by the definition of the residual indicator.

The theoretical analysis is complemented by numerical experiments for local polynomial degrees up to four. The experiments compare the linear and data-dependent compact multinode Shepard operators on both smooth and piecewise smooth data and investigate the influence of the nonlinear exponent.

The paper is organized as follows. Section 2 recalls the classical Shepard method and its compactly supported version. Section 3 reviews the multinode Shepard construction and introduces the compact multinode operator used throughout the paper. In Section 4 we define the data-dependent compact multinode Shepard method and the residual-based smoothness indicator. Section 5 is devoted to the theoretical properties of the new operator, including the behavior of the indicator, the structural properties of the nonlinear construction, and the convergence analysis in smooth regions and near a discontinuity. The numerical experiments are presented in Section 6, and concluding remarks are collected in Section 7.

Classical and compact Shepard methods

Following the notation of [16], let Ω\Omega be an open, connected and bounded subset of Rs\mathbb{R}^{s}, s∈Ns \in\mathbb{N}, and let X={x1,…,xn}⊂ΩX = \{x_1,\ldots,x_n\} \subset\Omega be a set of nodes. Given a function f:Ω→Rf:\Omega\to\mathbb{R} known only through the values fi=f(xi)f_i=f(x_i) at the nodes, the classical Shepard method [1] is defined by

Sμ[f](x)=∑i=1nAμ,i(x)fi,x∈Ω∖X,(1)S_{\mu}[f](x)=\sum_{i=1}^{n} A_{\mu,i}(x)f_i,\qquad x\in\Omega\setminus X, \tag*{(1)}

where, for a fixed parameter μ>0\mu>0, the Shepard weights Aμ,iA_{\mu,i}, i=1,…,ni=1,\ldots,n, are given by

Aμ,i(x)=∥x−xi∥−μ∑k=1n∥x−xk∥−μ,x∈Ω∖X.(2)A_{\mu,i}(x)=\frac{\lVert x-x_i\rVert^{-\mu}}{\sum_{k=1}^{n}\lVert x-x_k\rVert^{-\mu}},\qquad x\in\Omega\setminus X. \tag*{(2)}

Here ∥⋅∥\lVert\cdot\rVert denotes the Euclidean norm. At the data sites, the operator is defined by continuous extension, Sμ[f](xi)=fiS_{\mu}[f](x_i)=f_i, so that the method is interpolatory. The operator Sμ[f]S_{\mu}[f] is a partition of unity method (PUM), see e.g. [17], whose local approximants are the constant values fif_i, that is, polynomials of degree zero. The classical Shepard weights satisfy the standard partition of unity and interpolation properties established in [1, 18], which we recall below.

Proposition 2.1. The functions Aμ,iA_{\mu,i} defined in (2) satisfy

Aμ,i(x)≥0,i=1,…,n,∑i=1nAμ,i(x)=1,x∈Ω∖X,(3)A_{\mu,i}(x)\geq0,\qquad i=1,\ldots,n,\qquad\sum_{i=1}^{n}A_{\mu,i}(x)=1,\qquad x\in\Omega\setminus X, \tag*{(3)}

and

lim⁡x→xjAμ,i(x)=δij,DαAμ,i(xj)=0,1≤∣α∣<μ,i,j∈{1,…,n},\lim_{x\to x_j}A_{\mu,i}(x)=\delta_{ij},\qquad D^{\alpha}A_{\mu,i}(x_j)=0,\qquad1\leq\lvert\alpha\rvert<\mu,\qquad i,j\in\{1,\ldots,n\},

where δij\delta_{ij} is the Kronecker delta, α=(α1,…,αs)∈Ns\alpha=(\alpha_1,\ldots,\alpha_s)\in\mathbb{N}^{s} is a multi-index with ∣α∣=α1+⋯+αs\lvert\alpha\rvert=\alpha_1+\cdots+\alpha_s, Dα=∂∣α∣/∂x1α1⋯∂xsαsD^{\alpha}=\partial^{\lvert\alpha\rvert}/\partial x_1^{\alpha_1}\cdots\partial x_s^{\alpha_s}, and the derivatives are understood for the continuous extensions of the weights.

The regularity of these extensions depends on the parameter μ\mu, as recalled in the following result; see [18].

Proposition 2.2. The continuous extensions of the functions Aμ,iA_{\mu,i} are: C0C^{0} with cusps at the nodes if μ<1\mu<1; C0C^{0} with corners at the nodes if μ=1\mu=1; C⌊μ⌋C^{\lfloor\mu\rfloor} if μ>1\mu>1 and μ∉N\mu\notin\mathbb{N}; Cμ−1C^{\mu-1} if μ>1\mu>1 *is an odd integer; and C∞C^{\infty} rational functions with no real poles if μ>1\mu>1 is an even integer.

A compactly supported version of the Shepard method was introduced by Franke and Nielson [2] by replacing the global weights Aμ,iA_{\mu,i} with

A~μ,i(x)=(1∥x−xi∥−1Ri)+μ∑k=1n(1∥x−xk∥−1Rk)+μ,i=1,…,n.(4)\widetilde{A}_{\mu,i}(x)=\frac{\left(\dfrac{1}{\lVert x-x_i\rVert}-\dfrac{1}{R_i}\right)_{+}^{\mu}}{\sum_{k=1}^{n}\left(\dfrac{1}{\lVert x-x_k\rVert}-\dfrac{1}{R_k}\right)_{+}^{\mu}},\qquad i=1,\ldots,n. \tag*{(4)}

Here (z)+=max⁡{z,0}(z)_+ = \max\{z,0\}, and the weights are defined for

x∈⋃k=1nB(xk,Rk)∖X,x \in\bigcup_{k=1}^{n} B(x_k,R_k) \setminus X,

where B(xk,Rk)B(x_k,R_k) denotes the open Euclidean ball centered at xkx_k with radius Rk>0R_k > 0. The support radius RkR_k is typically chosen so that B(xk,Rk)B(x_k,R_k) contains a prescribed number of data sites [2]. As in the classical case, the definition is completed at the data sites by continuous extension.

Multinode Shepard method and compact multinode Shepard method

Dell’Accio et al. in [3, 4, 5] extend the idea of the Shepard method using polynomials of higher degree. Let d∈Nd \in\mathbb{N}, let Πd(Rs)\Pi_d(\mathbb{R}^s) denote the space of polynomials of total degree at most dd in ss variables, of dimension

m=(d+ss),m = \binom{d+s}{s},

and recall that a set of mm nodes is Πd(Rs)\Pi_d(\mathbb{R}^s)-unisolvent if every function defined on it admits a unique interpolant in Πd(Rs)\Pi_d(\mathbb{R}^s). Let

Sd={τ1,…,τr},τj={xj1,…,xjm}⊂X,\mathcal{S}_d = \{\tau_1,\ldots,\tau_r\}, \qquad\tau_j = \{x_{j1},\ldots,x_{jm}\} \subset X,

be a family of rr stencils, i.e. pairwise distinct unordered mm-subsets of XX, each consisting of pairwise distinct nodes, such that each τj\tau_j is Πd(Rs)\Pi_d(\mathbb{R}^s)-unisolvent and Sd\mathcal{S}_d is a covering of XX, i.e.

⋃j=1rτj=X.\bigcup_{j=1}^{r} \tau_j = X.

The multinode Shepard method is

Mμ[f](x)=∑j=1rWμ,j(x)Pj[f](x),x∈Ω∖X,(5)M_\mu[f](x) = \sum_{j=1}^{r} W_{\mu,j}(x) P_j[f](x), \qquad x \in\Omega\setminus X, \tag*{(5)}

with Pj[f]∈Πd(Rs)P_j[f] \in\Pi_d(\mathbb{R}^s) the unique interpolation polynomial on τj\tau_j and

Wμ,j(x)=∏i=1m∥x−xji∥−μ∑k=1r∏i=1m∥x−xki∥−μ,μ>0,(6)W_{\mu,j}(x) = \frac{\prod_{i=1}^{m}\lVert x-x_{ji}\rVert^{-\mu}} {\sum_{k=1}^{r}\prod_{i=1}^{m}\lVert x-x_{ki}\rVert^{-\mu}}, \qquad\mu> 0, \tag*{(6)}

completed by continuous extension at the data sites. The basic properties of the multinode weights established in [3] are recalled in the following proposition.

Proposition 3.1. The functions Wμ,jW_{\mu,j} satisfy, for x∈Ω∖Xx \in\Omega\setminus X: Wμ,j(x)≥0W_{\mu,j}(x) \ge0; ∑j=1rWμ,j(x)=1\sum_{j=1}^{r} W_{\mu,j}(x) = 1; lim⁡x→xiWμ,j(x)=0\lim_{x\to x_i} W_{\mu,j}(x) = 0 for all jj with xi∉τjx_i \notin\tau_j; and ∑k∈Jilim⁡x→xiWμ,k(x)=1\sum_{k\in J_i}\lim_{x\to x_i} W_{\mu,k}(x) = 1, where Ji={j:1≤j≤r, xi∈τj}J_i = \{j : 1 \le j \le r,\ x_i \in\tau_j\}. Moreover, the extended Wμ,jW_{\mu,j} satisfy the differentiability properties of Proposition 2.2.

Following the idea of Franke and Nielson [2], a compact multinode Shepard (CMS) operator was developed in [6] for scattered data interpolation on the torus, viewed as a smooth embedded manifold in R3\mathbb{R}^3. Here, we adopt the same localization principle and replace the global weights with

W~μ,j(x)=∏i=1m(1∥x−xji∥−1Rj)+μ∑k=1r∏i=1m(1∥x−xki∥−1Rk)+μ,j=1,…,r,(7)\widetilde{W}_{\mu,j}(x) = \frac{\prod_{i=1}^{m}\left(\frac{1}{\lVert x-x_{ji}\rVert}-\frac{1}{R_j}\right)_+^\mu} {\sum_{k=1}^{r}\prod_{i=1}^{m}\left(\frac{1}{\lVert x-x_{ki}\rVert}-\frac{1}{R_k}\right)_+^\mu}, \qquad j=1,\ldots,r, \tag*{(7)}

where truncation and exponent act factorwise in both numerator and denominator, and Rj>0R_j > 0 is a support radius associated with the stencil τj\tau_j, specified below. For x∈Ω∖Xx \in\Omega\setminus X, the unnormalized numerator associated with the jj-th stencil is positive if and only if ∥x−xji∥<Rj\lVert x-x_{j i}\rVert<R_j for every i=1,…,mi=1,\ldots,m. In order to determine the radii RjR_j we use the fill distance

hX,Ω=sup⁡x∈Ωmin⁡xi∈X∥x−xi∥,(8)h_{X,\Omega}=\sup_{x\in\Omega}\min_{x_i\in X}\lVert x-x_i\rVert, \tag*{(8)}

or rather a strict upper bound of it: throughout the paper, hh denotes a number satisfying h>hX,Ωh>h_{X,\Omega}. In practice, hh is chosen as a certified computable upper bound; see § 6, since the exact fill distance, defined through a supremum over Ω\Omega, is in general not directly computable. We then set

Rj=diam⁡(τj)+h,R_j=\operatorname{diam}(\tau_j)+h,

where

diam⁡(τj)=max⁡x,y∈τj∥x−y∥\operatorname{diam}(\tau_j)=\max_{x,y\in\tau_j}\lVert x-y\rVert

denotes the diameter of the stencil τj\tau_j, so that the support of W~μ,j\widetilde{W}_{\mu,j} is

Cj=⋂i=1m{y∈Rs:∥y−xji∥≤Rj}.C_j=\bigcap_{i=1}^{m}\left\{y\in\mathbb{R}^s:\lVert y-x_{j i}\rVert\le R_j\right\}.

which represents the intersection of the mm closed Euclidean balls of radius RjR_j centered at the nodes of the stencil τj\tau_j. This set is independent of μ\mu and of Ω\Omega, and int⁡(Cj)\operatorname{int}(C_j) denotes its interior in Rs\mathbb{R}^s, so that points of ∂Ω\partial\Omega are not excluded from the supports. For x∈Ωx\in\Omega, let

Jx={j:1≤j≤r, x∈int⁡(Cj)}.J_x=\{j:1\le j\le r,\ x\in\operatorname{int}(C_j)\}.

We say that xx is covered if Jx≠∅J_x\ne\varnothing, and we call the stencils τj\tau_j with j∈Jxj\in J_x active at xx. For a covered x∈Ω∖Xx\in\Omega\setminus X, the CMS operator is defined by

M~μ[f](x)=∑j∈JxW~μ,j(x)Pj[f](x).(9)\widetilde{M}_{\mu}[f](x)=\sum_{j\in J_x}\widetilde{W}_{\mu,j}(x)P_j[f](x). \tag*{(9)}

At the data sites, the definition is completed by continuous extension. The covering property ⋃j=1rτj=X\bigcup_{j=1}^{r}\tau_j=X, together with the strict inequality h>hX,Ωh>h_{X,\Omega}, ensures that the interiors of the supports cover Ω\Omega, as established in the following lemma.

Lemma 3.2. Assume that ⋃j=1rτj=X\bigcup_{j=1}^{r}\tau_j=X and h>hX,Ωh>h_{X,\Omega}. Then

Ω⊆⋃j=1rint⁡(Cj),\Omega\subseteq\bigcup_{j=1}^{r}\operatorname{int}(C_j),

and hence Jx≠∅J_x\ne\varnothing for every x∈Ωx\in\Omega. More precisely, if xix_i is a nearest data site to xx, then

x∈int⁡(Cj)x\in\operatorname{int}(C_j)

for every stencil τj\tau_j containing xix_i.

Proof. Fix x∈Ωx\in\Omega and let xi∈Xx_i\in X be a nearest data site to xx. Since the stencils cover XX, let τj\tau_j be any stencil containing xix_i. For every xjq∈τjx_{jq}\in\tau_j, the triangle inequality gives

∥x−xjq∥≤∥x−xi∥+∥xi−xjq∥≤hX,Ω+diam⁡(τj)<h+diam⁡(τj)=Rj.\lVert x-x_{jq}\rVert\le\lVert x-x_i\rVert+\lVert x_i-x_{jq}\rVert\le h_{X,\Omega}+\operatorname{diam}(\tau_j)<h+\operatorname{diam}(\tau_j)=R_j.

Thus x∈int⁡(Cj)x\in\operatorname{int}(C_j). Since x∈Ωx\in\Omega was arbitrary, the result follows.

Remark 3.3. The strict inequality h>hX,Ωh>h_{X,\Omega} is essential: with h=hX,Ωh=h_{X,\Omega} the points attaining the supremum in (8) may fall on support boundaries (for instance, for degree zero, Rj=hR_j=h, and a fill-distance maximizer is at distance at least hh from every node, with equality for at least one nearest node), and the operator would be undefined there. Any computable upper bound strictly larger than hX,Ωh_{X,\Omega} satisfies the hypothesis. If the exact fill distance is known, it is enough to increase it by an arbitrarily small positive amount.

Data-dependent compact multinode Shepard method: construction

In this section we introduce a nonlinear extension of the compact multinode Shepard method by incorporating data-dependent weights inspired by the WENO methodology [10]. In [11], the partition of unity structure of B-spline basis functions is exploited to introduce a nonlinear WENO-type weighting strategy; the same idea is applied to the classical Shepard method in [13]. Following these ideas, we define, for x∈Ω∖Xx \in\Omega\setminus X, the nonlinear operator

K~[f](x)=∑j∈JxB~μ,j[f](x)Pj[f](x),(10)\widetilde{K}[f](x) = \sum_{j \in J_x} \widetilde{B}_{\mu,j}[f](x) P_j[f](x), \tag*{(10)}

where

B~μ,j[f](x)=βμ,j[f](x)∑k∈Jxβμ,k[f](x),βμ,j[f](x)=W‾μ,j(x)(ϵ+Ij)t.(11)\widetilde{B}_{\mu,j}[f](x) = \frac{\beta_{\mu,j}[f](x)}{\sum_{k \in J_x} \beta_{\mu,k}[f](x)}, \qquad\beta_{\mu,j}[f](x) = \frac{\overline{W}_{\mu,j}(x)}{(\epsilon+ I_j)^t}. \tag*{(11)}

Here Ij≥0I_j \ge0 is a smoothness indicator associated with the stencil τj\tau_j, while t≥1t \ge1 and ϵ>0\epsilon> 0 are parameters. The exponent tt controls the damping of non-smooth contributions, whereas ϵ\epsilon ensures that the denominator in the definition of βμ,j[f]\beta_{\mu,j}[f] remains strictly positive. For the asymptotic analysis, we take ϵ=ϵ(h)≤hd+1\epsilon= \epsilon(h) \le h^{d+1} and complete the definition of the operator at the data sites by setting

K~[f](xi)=fi,i=1,…,n.\widetilde{K}[f](x_i) = f_i, \qquad i = 1,\ldots,n.

Since Pj[f]P_j[f] interpolates ff on τj\tau_j, the residuals at the stencil nodes vanish identically and therefore provide no information on the local regularity. In contrast to the degree-zero setting of [13], where the indicator is constructed from an auxiliary least-squares fit, here the residuals must be evaluated at nodes outside τj\tau_j. Since these nodes belong to XX, no additional function evaluations are required, as the same local interpolant Pj[f]P_j[f] can be evaluated at them.

Definition 4.1. For j=1,…,rj = 1,\ldots,r, let Ej⊆X∖τjE_j \subseteq X \setminus\tau_j be a nonempty indicator set with ∣Ej∣≤NE|E_j| \le N_E and dist⁡(y,τj)≤cEh\operatorname{dist}(y,\tau_j) \le c_E h for every y∈Ejy \in E_j, where NE∈NN_E \in\mathbb{N} and cE>0c_E > 0 are constants independent of jj and hh, ∣F∣|F| denotes the cardinality of a finite set FF, and dist⁡(y,τj)=min⁡i∥y−xji∥\operatorname{dist}(y,\tau_j) = \min_i \lVert y - x_{j_i} \rVert. The smoothness indicator associated with τj\tau_j is

Ij=1∣Ej∣∑xi∈Ej∣f(xi)−Pj[f](xi)∣.(12)I_j = \frac{1}{|E_j|} \sum_{x_i \in E_j} |f(x_i) - P_j[f](x_i)|. \tag*{(12)}

In the implementation, where s=2s = 2, we take Ej=Ni∖τjE_j = N_i \setminus\tau_j, where NiN_i is the neighborhood of the seed xix_i of τj\tau_j, from which the stencil is extracted during the stencil selection (§ 5); this set is nonempty, since ∣Ni∣≥12(d+2)(d+3)>m|N_i| \ge\frac{1}{2}(d+2)(d+3) > m, and it reuses the neighborhood already constructed by the search procedure. For the quasi-uniform node sets of Section 5, this choice satisfies the requirements of Definition 4.1 with NEN_E and cEc_E independent of hh: NiN_i is contained in a square of side proportional to hh centered at a node of τj\tau_j, and such a square contains a number of nodes bounded independently of hh. This is the choice used in all the numerical experiments of Section 6. The behavior of the indicator is analyzed in Lemma 5.2. In smooth regions, (12) is O(hd+1)O(h^{d+1}); moreover, when the stencil lies on one side of the discontinuity and its indicator set contains nodes on the other side, the indicator is uniformly bounded away from zero. Remark 5.6 shows, through an explicit configuration, that such a lower bound does not extend to arbitrary stencils crossing the discontinuity.

Properties of the new operator

Throughout this section XX is quasi-uniform and the upper bound hh of Section 3 is taken within the quasi-uniformity window: there exists cqu>0c_{\mathrm{qu}} > 0, independent of nn, such that

qX≤hX,Ω<h≤cquqX.q_X \le h_{X,\Omega} < h \le c_{\mathrm{qu}} q_X.

where

qX:=12min⁡i≠k∥xi−xk∥q_X := \frac{1}{2}\min_{i\ne k}\lVert x_i-x_k\rVert

is the separation distance. The first inequality uses the connectedness of Ω\Omega. Let xa∈Xx_a \in X; since Ω\Omega contains points arbitrarily close to xax_a and, for n≥2n \ge2, points arbitrarily close to a node xbx_b with ∥xb−xa∥≥2qX\lVert x_b-x_a\rVert\ge2q_X, it meets both B(xa,qX)B(x_a,q_X) and the complement of B(xa,qX)‾\overline{B(x_a,q_X)}; being open and connected, it is not the union of these two disjoint open sets, hence it contains a point pp with ∥p−xa∥=qX\lVert p-x_a\rVert=q_X. For every other node xcx_c, ∥p−xc∥≥∥xc−xa∥−∥p−xa∥≥qX\lVert p-x_c\rVert\ge\lVert x_c-x_a\rVert-\lVert p-x_a\rVert\ge q_X, so that dist⁡(p,X)=qX\operatorname{dist}(p,X)=q_X and hX,Ω≥qXh_{X,\Omega}\ge q_X. The argument also holds for X⊂Ω‾X\subset\overline{\Omega}. All the estimates below are stated in terms of hh; since hh and hX,Ωh_{X,\Omega} are comparable, the corresponding orders are the same, and hh is also the quantity used in the numerical experiments. For each stencil Tj\mathcal{T}_j, we set

aj:=1m∑i=1mxji,a_j := \frac{1}{m}\sum_{i=1}^{m}x_{ji},

the barycenter of Tj\mathcal{T}_j.

Assumption 5.1. There exist constants c1,σ0>0c_1,\sigma_0>0, independent of hh, such that for every j=1,…,rj=1,\ldots,r:

(i) diam⁡(Tj)≤c1h\operatorname{diam}(\mathcal{T}_j)\le c_1h;

(ii) denoting by VjV_j the Vandermonde matrix of a fixed basis of Πd(Rs)\Pi_d(\mathbb{R}^s) at the scaled nodes (xji−aj)/h(x_{ji}-a_j)/h, the smallest singular value of VjV_j satisfies σmin⁡(Vj)≥σ0\sigma_{\min}(V_j)\ge\sigma_0.

Setting c2:=c1+max⁡{1,cE}c_2:=c_1+\max\{1,c_E\}, with cEc_E the constant of Definition 4.1, Assumption 5.1(i) and the definition Rj=diam⁡(Tj)+hR_j=\operatorname{diam}(\mathcal{T}_j)+h give

Rj≤c2h.R_j\le c_2h.

Moreover, every y∈Cj‾y\in\overline{C_j} (in particular every node of Tj\mathcal{T}_j) satisfies

∥y−aj∥≤1m∑i=1m∥y−xji∥≤Rj≤c2h.(13)\lVert y-a_j\rVert\le\frac{1}{m}\sum_{i=1}^{m}\lVert y-x_{ji}\rVert\le R_j\le c_2h. \tag*{(13)}

Every point yy of an indicator set Ej\mathcal{E}_j satisfies ∥y−aj∥≤dist⁡(y,Tj)+diam⁡(Tj)≤c2h\lVert y-a_j\rVert\le\operatorname{dist}(y,\mathcal{T}_j)+\operatorname{diam}(\mathcal{T}_j)\le c_2h as well. Thus all the local objects involved below lie in the closed ball B(aj,c2h)B(a_j,c_2h).

Condition (ii) is a scale-invariant stability requirement. For fixed ss, dd, c1c_1 and cEc_E, the lower bound σmin⁡(Vj)≥σ0\sigma_{\min}(V_j)\ge\sigma_0, together with the locality condition in (i), implies a uniform bound Λ=Λ(s,d,c1,cE,σ0)\Lambda=\Lambda(s,d,c_1,c_E,\sigma_0) on the local Lebesgue constants of the interpolation operators f↦Pj[f]f\mapsto P_j[f] on the balls B(aj,c2h)B(a_j,c_2h), by a standard finite-dimensional argument. Condition (i), in turn, reflects the locality of the neighborhood-based stencil construction used in the implementation.

In the implementation, where s=2s=2, the family Sd\mathcal{S}_d is built by a minimal-covering construction, as in [16], in which each stencil is extracted from a local neighborhood by a discrete Leja-type selection based on LU factorization with row pivoting [19]. The nodes of XX are visited in a fixed order, and a new stencil is built only when a node not yet contained in any stencil is met, which keeps the number of stencils small (hence the name). For such a node xix_i, the seed, the construction proceeds as follows.

  1. Neighborhood. Let Ni\mathcal{N}_i be the set of nodes of XX in the square of side ℓ=(12(d+2)(d+3)area⁡(Q)/n)1/2\ell=\left(\frac{1}{2}(d+2)(d+3)\operatorname{area}(\mathcal{Q})/n\right)^{1/2} centered at the seed, where Q\mathcal{Q} is the bounding box of XX and n=∣X∣n=|X| is the number of nodes. If this square contains fewer than 12(d+2)(d+3)\frac{1}{2}(d+2)(d+3) nodes, it is enlarged by the factors 1+k/101+k/10, k=1,2,…k=1,2,\ldots, until it does. The side ℓ\ell is chosen so that the square contains, on average, 12(d+2)(d+3)=dim⁡Πd+1(R2)\frac{1}{2}(d+2)(d+3)=\dim\Pi_{d+1}(\mathbb{R}^2) nodes, more than the m=12(d+1)(d+2)m=\frac{1}{2}(d+1)(d+2) nodes of a stencil: the selection in the next steps has nodes to choose from, and the indicator set Ej=Ni∖Tj\mathcal{E}_j=\mathcal{N}_i\setminus\mathcal{T}_j of Section 4 is nonempty.

  1. Leja ordering. The nodes of Ni\mathcal{N}_i are listed by increasing distance from the seed, and their Vandermonde matrix is formed in the monomial basis centered at the barycenter of Ni\mathcal{N}_i, with the monomials in graded lexicographic order up to the smallest degree dˉ\bar d such that dim⁡Πdˉ(R2)≥∣Ni∣\dim\Pi_{\bar d}(\mathbb{R}^2)\ge|\mathcal{N}_i|. LU factorization with

row pivoting, carried to completion, orders the nodes of Ni\mathcal{N}_i as a nested discrete Leja sequence ξ1,ξ2,…\xi_1, \xi_2, \ldots [19]: at each step the pivot row is the node that maximizes, in absolute value, the determinant of the leading block of the matrix. The first column of the matrix is constant, so that the first pivot is a tie among all the rows, resolved in favour of the first one: ξ1\xi_1 is the seed. Since the basis is graded, the first mm elements of the sequence do not depend on dˉ\bar{d}.

  1. Candidate stencil. The candidate is {ξ1,…,ξm}\{\xi_1,\ldots,\xi_m\}, the first mm nodes of the Leja sequence. It contains the seed, and the greedy choice of the pivots promotes well-conditioned, hence unisolvent, configurations; unisolvence is in any case guaranteed by the check of the next step, since σmin⁡(Vj)≥σ0>0\sigma_{\min}(V_j) \ge\sigma_0 > 0.

  1. Conditioning check and replacement. The candidate is accepted if σmin⁡(Vj)≥σ0\sigma_{\min}(V_j) \ge\sigma_0, with VjV_j the scaled Vandermonde matrix of Assumption 5.1(ii) and σ0\sigma_0 a prescribed threshold. Otherwise, the node ξm+1\xi_{m+1} replaces in turn ξm,ξm−1,…,ξ2\xi_m,\xi_{m-1},\ldots,\xi_2, then ξm+2\xi_{m+2} does the same, and so on: each candidate differs from {ξ1,…,ξm}\{\xi_1,\ldots,\xi_m\} in a single node, its barycenter aja_j and its matrix VjV_j are recomputed, and the first candidate satisfying the bound is accepted. The seed is never replaced. If the sequence is exhausted without success, the neighborhood is enlarged by the same factors 1+k/101+k/10, at most ten more times, and steps 2–4 are repeated.

  1. Marking. The nodes of the accepted stencil τj\tau_j are marked as used, and the visit of XX continues with the next unused node.

Two aspects of this procedure deserve a comment. First, the Vandermonde matrix of step 2 may be rank deficient: on gridded neighborhoods, for instance, the polynomial u3−uu^3-u, with uu the first coordinate, vanishes on {−1,0,1}2\{-1,0,1\}^2. A column with vanishing pivot gives no selection criterion, and the corresponding node is taken in the order returned by the factorization. This may change the order in which the candidates of step 4 are tried, and hence the stencil that is accepted, but not its properties, since the bound σmin⁡(Vj)≥σ0\sigma_{\min}(V_j) \ge\sigma_0 is checked directly on every accepted stencil. Second, the threshold of step 4 is needed: the greedy selection of step 3 promotes well-conditioned configurations, but it does not by itself guarantee (ii) uniformly in hh. On Halton nodes with d=1d=1, for instance, the smallest value of σmin⁡(Vj)\sigma_{\min}(V_j) over the candidates of step 3 decreases from 0.26 to 0.045 between l=4l=4 and l=7l=7 in the notation of Section 6.

The properties required in this section follow from the construction. Every node is either a seed or a node of a previously built stencil, so that ⋃jτj=X\bigcup_j \tau_j = X; the stencils are pairwise distinct, since each of them contains a node, its seed, not used before; and (ii) holds with the prescribed σ0\sigma_0 for every accepted stencil. As for (i), for quasi-uniform XX the side ℓ\ell is bounded above and below by multiples of hh, and a square of side proportional to hh centered at a node contains the required number of nodes, so that the number of enlargements in steps 1 and 4 is bounded independently of hh; since the replacing nodes of step 4 belong to the neighborhood, every stencil lies in a square of side proportional to hh, and (i) holds with an hh-independent constant c1c_1. The procedure may fail to find a candidate satisfying the bound of step 4, in which case the implementation keeps the candidate with the largest σmin⁡(Vj)\sigma_{\min}(V_j) and reports the failure; this never occurred in the experiments of Section 6, which use σ0=0.05\sigma_0 = 0.05.

No regularity of ∂Ω\partial\Omega enters the proofs below, since Assumption 5.1 and the Cd+1C^{d+1} extensions of the target functions are required explicitly. Some regularity is, however, needed for these hypotheses to be satisfiable with hh-independent constants: near ∂Ω\partial\Omega, well-conditioned stencils of diameter O(h)O(h) exist if Ω\Omega satisfies an interior cone condition, and every f∈Cd+1(Ω‾)f \in C^{d+1}(\overline{\Omega}) admits the required extension if, for instance, Ω\Omega is a bounded Lipschitz domain: such domains are quasiconvex, i.e. they have Whitney’s property (P), and for regions with this property every function of class Cd+1C^{d+1} whose derivatives of order d+1d+1 extend continuously to ∂Ω\partial\Omega can be extended to a Cd+1C^{d+1} function on Rs\mathbb{R}^s [20], by means of Whitney’s extension theorem [21]. Both conditions hold for the square used in Section 6. Under Assumption 5.1, standard estimates for polynomial interpolation on unisolvent sets give, for g∈Cd+1(B‾(aj,c2h))g \in C^{d+1}(\overline{B}(a_j,c_2h)) and every y∈B‾(aj,c2h)y \in\overline{B}(a_j,c_2h),

∣g(y)−Pj[g](y)∣≤CΛhd+1∣g∣d+1,B(aj,c2h),∣g∣d+1,A:=max⁡∣α∣=d+1∥Dαg∥∞,A,(14)|g(y)-P_j[g](y)| \le C\Lambda h^{d+1}|g|_{d+1,B(a_j,c_2h)}, \qquad|g|_{d+1,A} := \max_{|\alpha|=d+1}\|D^\alpha g\|_{\infty,A}, \tag*{(14)}

with C=C(s,d,c1,cE)C=C(s,d,c_1,c_E); here ∥g∥∞,A=sup⁡A∣g∣\|g\|_{\infty,A}=\sup_A|g| for a set AA, and the subscript is omitted when the set is clear from the context. Throughout the paper, CC denotes a constant depending only on the parameters indicated at each occurrence, whose value may change from one occurrence to the next.

Detection properties of the indicator

We consider a piecewise smooth target. Let Γ⊂Ω\Gamma\subset\Omega be a C1C^{1} separating hypersurface, given as the zero set of γ∈C1(Ω)\gamma\in C^{1}(\Omega) with ∇γ≠0\nabla\gamma\ne0 on a tubular neighborhood T\mathcal{T} of Γ\Gamma of uniform width, that is, T⊃{x∈Ω:dist⁡(x,Γ)<δT}\mathcal{T} \supset\{x \in\Omega: \operatorname{dist}(x,\Gamma) < \delta_{\mathcal{T}}\} for some δT>0\delta_{\mathcal{T}} > 0; set Ω+={γ≥0}\Omega^{+} = \{\gamma\ge0\}, Ω−=Ω∖Ω+\Omega^{-} = \Omega\setminus\Omega^{+} (points of Γ\Gamma belong to Ω+\Omega^{+}), and

f~(x)={f1(x),x∈Ω+,f2(x),x∈Ω−.(15)\widetilde{f}(x) = \begin{cases} f_{1}(x), & x \in\Omega^{+},\\ f_{2}(x), & x \in\Omega^{-}. \end{cases} \tag*{(15)}

We assume that f1f_{1} and f2f_{2} admit extensions of class Cd+1C^{d+1} to fixed open sets U+⊃Ω+‾∪TU_{+} \supset\overline{\Omega^{+}} \cup\mathcal{T} and U−⊃Ω−‾∪TU_{-} \supset\overline{\Omega^{-}} \cup\mathcal{T}, respectively. The branch seminorms ∣f1∣d+1|f_{1}|_{d+1} and ∣f2∣d+1|f_{2}|_{d+1} are taken on U+U_{+} and U−U_{-}, respectively, and are therefore independent of hh. We also assume that, for some h0>0h_{0} > 0 and all h≤h0h \le h_{0}, the balls B(aj,c2h)B(a_{j},c_{2}h) appearing below are contained in the relevant U±U_{\pm}, and that the jump satisfies ∣f1−f2∣≥J0>0|f_{1}-f_{2}| \ge J_{0} > 0 on T\mathcal{T}.

Lemma 5.2. Let Assumption 5.1 hold and let τj∪Ej⊂B(aj,c2h)\tau_{j} \cup\mathcal{E}_{j} \subset B(a_{j},c_{2}h), with B(aj,c2h)B(a_{j},c_{2}h) contained in the domain of the relevant extension.

(P1) If ff coincides on B(aj,c2h)B(a_{j},c_{2}h) with a function of class Cd+1C^{d+1}, then

Ij≤CΛhd+1∣f∣d+1,B(aj,c2h).I_{j} \le C\Lambda h^{d+1}|f|_{d+1,B(a_{j},c_{2}h)}.

(P2) If the datum is f~\widetilde{f} of (15), and τj⊂Ω+\tau_{j} \subset\Omega^{+} while Ej\mathcal{E}_{j} contains at least one point of Ω−∩T\Omega^{-} \cap\mathcal{T}, or τj⊂Ω−\tau_{j} \subset\Omega^{-} while Ej\mathcal{E}_{j} contains at least one point of Ω+∩T\Omega^{+} \cap\mathcal{T}, then

Ij≥J02NE>0I_{j} \ge\frac{J_{0}}{2N_{E}} > 0

for all hh small enough.

Proof. (P1) is immediate from (14). For (P2), let xi∈Ej∩Ω−∩Tx_{i} \in\mathcal{E}_{j} \cap\Omega^{-} \cap\mathcal{T}. Since τj⊂Ω+\tau_{j} \subset\Omega^{+}, Pj[f~]=Pj[f1]P_{j}[\widetilde{f}] = P_{j}[f_{1}] interpolates the extended smooth branch f1f_{1} and, by (14) applied to the extension,

∣f1(xi)−Pj[f~](xi)∣≤CΛhd+1∣f1∣d+1.|f_{1}(x_{i}) - P_{j}[\widetilde{f}](x_{i})| \le C\Lambda h^{d+1}|f_{1}|_{d+1}.

Since xi∈Tx_{i} \in\mathcal{T}, we have ∣f2(xi)−f1(xi)∣≥J0|f_{2}(x_{i}) - f_{1}(x_{i})| \ge J_{0}. Hence

∣f~(xi)−Pj[f~](xi)∣≥∣f2(xi)−f1(xi)∣−∣f1(xi)−Pj[f~](xi)∣≥J0−CΛhd+1∣f1∣d+1≥J02\begin{aligned} |\widetilde{f}(x_{i}) - P_{j}[\widetilde{f}](x_{i})| \ge|f_{2}(x_{i}) - f_{1}(x_{i})| - |f_{1}(x_{i}) - P_{j}[\widetilde{f}](x_{i})| \\ &\ge J_{0} - C\Lambda h^{d+1}|f_{1}|_{d+1} \ge\frac{J_{0}}{2} \end{aligned}

for hh small enough. The claim then follows from

Ij≥∣f~(xi)−Pj[f~](xi)∣NE.I_{j} \ge\frac{|\widetilde{f}(x_{i}) - P_{j}[\widetilde{f}](x_{i})|}{N_{E}}.

In the opposite case no node of τj\tau_{j} lies on Γ⊂Ω+\Gamma\subset\Omega^{+}, so that Pj[f~]=Pj[f2]P_{j}[\widetilde{f}] = P_{j}[f_{2}], and the same argument applies with f1f_{1} and f2f_{2} exchanged. □\square

Lemma 5.2(P2) provides a sufficient detection condition: it covers stencils that lie on one side of Γ\Gamma while their indicator set reaches the opposite side within the tubular neighborhood T\mathcal{T}. If Ω\Omega is convex, the latter requirement is not restrictive for small hh: the segment joining a node of τj\tau_{j} to a point of Ej∩Ω−\mathcal{E}_{j} \cap\Omega^{-} lies in Ω∩B(aj,c2h)\Omega\cap B(a_{j},c_{2}h) and, by continuity of γ\gamma, meets Γ\Gamma, so that every point of Ej∩Ω−\mathcal{E}_{j} \cap\Omega^{-} lies within 2c2h2c_{2}h of Γ\Gamma and hence in T\mathcal{T} for hh small enough. In a nonconvex domain, a point of Ej∩Ω−\mathcal{E}_{j} \cap\Omega^{-} may instead be close to τj\tau_{j} across ∂Ω\partial\Omega rather than across Γ\Gamma, and the restriction to T\mathcal{T} is then essential. Lemma 5.2(P2) does not cover stencils whose interpolation nodes themselves straddle Γ\Gamma; Remark 5.6 in § 5.4 shows, by an explicit configuration, that this limitation is essential.

Structural properties

Proposition 5.3. For every ff and every choice of ϵ>0\epsilon> 0, t≥1t \ge1:

(a) B~μ,j[f](x)≥0\widetilde{B}_{\mu,j}[f](x) \ge0 and

∑j∈JxB~μ,j[f](x)=1\sum_{j \in J_x} \widetilde{B}_{\mu,j}[f](x) = 1

for every covered x∉Xx \notin X; consequently, K~\widetilde{K} reproduces Πd(Rs)\Pi_d(\mathbb{R}^s) on the covered set.

(b) The definition of K~[f]\widetilde{K}[f], given by (10) for x∉Xx \notin X and by K~[f](xi)=fi\widetilde{K}[f](x_i) = f_i at the data sites, is continuous: for every xi∈Xx_i \in X,

lim⁡x→xiK~[f](x)=fi.\lim_{x \to x_i} \widetilde{K}[f](x) = f_i.

(c) On Ω∖X\Omega\setminus X, K~[f]\widetilde{K}[f] has at least the regularity guaranteed by the compact weights, namely C⌊μ⌋C^{\lfloor\mu\rfloor} if μ∉N\mu\notin\mathbb{N} and Cμ−1C^{\mu-1} if μ∈N\mu\in\mathbb{N}. In particular, even integer values of μ\mu do not yield C∞C^\infty regularity across support boundaries.

(d) For every covered x∉Xx \notin X,

min⁡j∈JxPj[f](x)≤K~[f](x)≤max⁡j∈JxPj[f](x).\min_{j \in J_x} P_j[f](x) \le\widetilde{K}[f](x) \le\max_{j \in J_x} P_j[f](x).

Proof. For x∈Ω∖Xx \in\Omega\setminus X, define the unnormalized compact weights by

W~μ,j(x):=∏ν=1m(1∥x−xjν∥−1Rj)μ,j=1,…,r,\widetilde{W}_{\mu,j}(x) := \prod_{\nu=1}^{m} \left(\frac{1}{\lVert x-x_{j_\nu}\rVert} - \frac{1}{R_j}\right)^\mu,\qquad j=1,\ldots,r,

and set

ωj:=(ϵ+Ij)−t>0.\omega_j := (\epsilon+ I_j)^{-t} > 0.

Substituting the expression of W~μ,j\widetilde{W}_{\mu,j} from (7) into (11), we obtain, for j∈Jxj \in J_x,

B~μ,j[f](x)=ωjW~μ,ju(x)∑k=1rωkW~μ,ku(x).(16)\widetilde{B}_{\mu,j}[f](x) = \frac{\omega_j\widetilde{W}_{\mu,j}^{u}(x)} {\sum_{k=1}^{r}\omega_k\widetilde{W}_{\mu,k}^{u}(x)}. \tag*{(16)}

Indeed, W~μ,ku(x)=0\widetilde{W}_{\mu,k}^{u}(x)=0 whenever k∉Jxk \notin J_x.

(a) Nonnegativity and normalization follow immediately from (16). If p∈Πd(Rs)p \in\Pi_d(\mathbb{R}^s), then Pj[p]=pP_j[p] = p by unisolvence, and hence, for x∉Xx \notin X,

K~[p](x)=p(x)∑j∈JxB~μ,j[p](x)=p(x).\widetilde{K}[p](x)=p(x)\sum_{j\in J_x}\widetilde{B}_{\mu,j}[p](x)=p(x).

At the data sites, polynomial reproduction follows directly from the definition of K~\widetilde{K}.

(b) Fix xi∈Xx_i \in X and set

ρ:=∥x−xi∥,\rho:= \lVert x-x_i\rVert,

and let Ji={j:xi∈τj}J_i=\{j:x_i\in\tau_j\} be the set introduced in Proposition 3.1. The set JiJ_i is nonempty since the stencil family covers XX. Let j∈Jij\in J_i and let xjq=xix_{jq}=x_i. Then

ρμW~μ,ju(x)⟶wij:=∏ν=1ν≠qm(1∥xi−xjν∥−1Rj)μ>0\rho^\mu\widetilde{W}_{\mu,j}^{u}(x)\longrightarrow w_{ij}:=\prod_{\substack{\nu=1\\\nu\ne q}}^{m}\left(\frac{1}{\lVert x_i-x_{j_\nu}\rVert}-\frac{1}{R_j}\right)^\mu>0

as x→xix \to x_i. Indeed,

∥xi−xjν∥≤diam⁡(τj)<Rj,ν≠q,\lVert x_i-x_{j\nu}\rVert\le\operatorname{diam}(\tau_j)<R_j,\qquad\nu\ne q,

so all the remaining factors have positive finite limits.

If j∉Jij\notin J_i, no factor of W~μ,ju\widetilde{W}_{\mu,j}^{u} is singular at xix_i, and therefore

W~μ,ju(x)=O(1),ρμW~μ,ju(x)⟶0.\widetilde{W}_{\mu,j}^{u}(x)=O(1),\qquad\rho^\mu\widetilde{W}_{\mu,j}^{u}(x)\longrightarrow0.

Consequently,

ρμ∑k=1rωkW~μ,ku(x)⟶∑k∈Jiωkwik>0.\rho^\mu\sum_{k=1}^{r}\omega_k\widetilde{W}_{\mu,k}^{u}(x)\longrightarrow\sum_{k\in J_i}\omega_k w_{ik}>0.

It follows from (16) that

B~μ,j[f](x)⟶{ωjwij∑k∈Jiωkwik,j∈Ji,0,j∉Ji.\widetilde{B}_{\mu,j}[f](x)\longrightarrow \begin{cases} \dfrac{\omega_j w_{ij}}{\sum_{k\in J_i}\omega_k w_{ik}}, & j\in J_i,\\ 0, & j\notin J_i. \end{cases}

The nonzero limits are nonnegative and sum to one. Since Pj[f](xi)=fiP_j[f](x_i)=f_i for every j∈Jij\in J_i, we conclude that

lim⁡x→xiK~[f](x)=∑j∈Jiωjwij∑k∈JiωkwikPj[f](xi)=fi.\lim_{x\to x_i}\widetilde{K}[f](x)=\sum_{j\in J_i}\dfrac{\omega_j w_{ij}}{\sum_{k\in J_i}\omega_k w_{ik}}P_j[f](x_i)=f_i.

(c) For fixed ff, the coefficients ωj\omega_j in (16) are positive constants with respect to xx. Away from the data sites, a factor of W~μ,ju\widetilde{W}_{\mu,j}^{u} may lose smoothness only across a support boundary

∥x−xjν∥=Rj.\lVert x-x_{j\nu}\rVert=R_j.

Writing ρ(x)=∥x−xjν∥\rho(x)=\lVert x-x_{j\nu}\rVert, near such a boundary one has

(1ρ(x)−1Rj)+μ=(Rj−ρ(x))+μ(ρ(x)Rj)μ.\left(\frac{1}{\rho(x)}-\frac{1}{R_j}\right)_{+}^{\mu}=\frac{(R_j-\rho(x))_{+}^{\mu}}{(\rho(x)R_j)^\mu}.

The denominator is smooth and strictly positive there, so the regularity is governed by (Rj−ρ(x))+μ(R_j-\rho(x))_{+}^{\mu}. Hence each factor is of class C⌊μ⌋C^{\lfloor\mu\rfloor} if μ∉N\mu\notin\mathbb{N} and Cμ−1C^{\mu-1} if μ∈N\mu\in\mathbb{N}. Products and finite sums preserve at least this regularity. Moreover, the denominator in (16) is strictly positive on Ω∖X\Omega\setminus X by the covering property. Therefore the nonlinear weights, and hence K~[f]\widetilde{K}[f], have the stated regularity on Ω∖X\Omega\setminus X, since the local approximants Pj[f]P_j[f] are polynomials. At the data sites, part (b) guarantees continuity; higher regularity there is not addressed here.

(d) By part (a), K~[f](x)\widetilde{K}[f](x) is a convex combination of the values Pj[f](x)P_j[f](x). Therefore,

min⁡j∈JxPj[f](x)≤K~[f](x)≤max⁡j∈JxPj[f](x).\min_{j\in J_x}P_j[f](x)\le\widetilde{K}[f](x)\le\max_{j\in J_x}P_j[f](x).

Convergence in smooth regions

Theorem 5.4 (order in smooth regions). Let Assumption 5.1 hold and let ff admit a Cd+1C^{d+1} extension to a fixed open set containing

⋃jB(aj,c2h)‾\bigcup_j \overline{B(a_j,c_2h)}

for all sufficiently small hh. Then, for any ϵ>0\epsilon>0 and t≥1t\ge1,

∥f−K~[f]∥∞,Ω≤Chd+1∣f∣d+1,\lVert f-\widetilde{K}[f]\rVert_{\infty,\Omega}\le C h^{d+1}|f|_{d+1},

where C=C(s,d,c1,cE,σ0)C=C(s,d,c_1,c_E,\sigma_0) is independent of hh, ϵ\epsilon and tt, and ∣f∣d+1|f|_{d+1} denotes the seminorm of the extension.

Proof. Fix x∈Ω∖Xx \in\Omega\setminus X. By Lemma 3.2, Jx≠∅J_x \ne\emptyset. For every j∈Jxj \in J_x, one has x∈Cjx \in C_j, and hence (13) gives

∥x−aj∥≤c2h.\lVert x-a_j\rVert\le c_2h.

Therefore x∈B(aj,c2h)x \in B(a_j,c_2h), and (14) yields

∣f(x)−Pj[f](x)∣≤Chd+1∣f∣d+1.\lvert f(x)-P_j[f](x)\rvert\le Ch^{d+1}\lvert f\rvert_{d+1}.

Using Proposition 5.3(a),

∣f(x)−K~[f](x)∣=∣∑j∈JxB~μ,j[f](x)(f(x)−Pj[f](x))∣≤∑j∈JxB~μ,j[f](x)∣f(x)−Pj[f](x)∣≤Chd+1∣f∣d+1.\begin{aligned} \left\lvert f(x)-\widetilde{K}[f](x)\right\rvert &=\left\lvert\sum_{j\in J_x}\widetilde{B}_{\mu,j}[f](x)\left(f(x)-P_j[f](x)\right)\right\rvert\\ &\le\sum_{j\in J_x}\widetilde{B}_{\mu,j}[f](x)\left\lvert f(x)-P_j[f](x)\right\rvert\\ &\le Ch^{d+1}\lvert f\rvert_{d+1}. \end{aligned}

At the data sites the estimate is immediate from interpolation. Taking the supremum over Ω\Omega proves the result. No additional restriction on tt or ϵ\epsilon is needed: in a smooth region all active local interpolants already achieve the same O(hd+1)O(h^{d+1}) accuracy, and any convex combination of them preserves this order.

Behaviour near a discontinuity

Let f~\widetilde{f} be as in (15) and fix an evaluation point x∈Ω±∖Xx \in\Omega^{\pm} \setminus X. By Lemma 3.2, Jx≠∅J_x \ne\emptyset. We call an active stencil j∈Jxj \in J_x one-sided if

τj⊂Ω+orτj⊂Ω−,\tau_j \subset\Omega^+ \qquad\text{or} \qquad\tau_j \subset\Omega^-,

and straddling otherwise.

Assumption 5.5 (indicator separation at xx). There exist θ,γ0∈(0,1)\theta,\gamma_0 \in(0,1) and CG,cB>0C_G,c_B>0, independent of hh, such that:

(A1) if x∈Ω+x \in\Omega^+ (respectively, x∈Ω−x \in\Omega^-), then every one-sided active stencil satisfies τj⊂Ω+\tau_j \subset\Omega^+ (respectively, τj⊂Ω−\tau_j \subset\Omega^-);

(A2) there exists a one-sided active stencil j∗∈Jxj^* \in J_x such that

∥x−xji∥≤(1−θ)Rj∗,i=1,…,m,\lVert x-x_{j_i}\rVert\le(1-\theta)R_{j^*}, \qquad i=1,\ldots,m,

and

Ij∗≤CGhd+1;I_{j^*} \le C_Gh^{d+1};

(A3) every active stencil j∈Jxj \in J_x that is not one-sided satisfies

Ij≥cB;I_j \ge c_B;

(A4) every active stencil j∈Jxj \in J_x that is not one-sided satisfies

∥x−xji∥≥γ0qX,i=1,…,m.\lVert x-x_{j_i}\rVert\ge\gamma_0q_X, \qquad i=1,\ldots,m.

The four conditions have the following meaning. Condition (A1) excludes one-sided active stencils belonging to the opposite branch. Such a stencil interpolates smooth data and has a small indicator, exactly like the one-sided stencils of the correct branch, so that the nonlinear weighting cannot tell the two apart: if it is active, it contributes a value of the wrong branch with a weight of order one, and the error at xx is of the order of the jump. This is what happens at the few points near the corner of the square geometry of § 6 where the operator loses accuracy.

Condition (A2) requires a reference stencil: one-sided, on the correct side, smooth in the sense of the indicator, and with xx at a positive distance from the boundary of its support. The geometric margin plays the same role as the lower-bound condition imposed on the radial weight in [13 Theorem 3]: it prevents the unnormalized weight of the reference stencil from becoming arbitrarily small near the boundary of its support, and it is with this weight that the weights of the straddling stencils are compared in the proof. The bound

Ij∗≤CGhd+1I_{j^\ast} \le C_G h^{d+1}

holds, by Lemma 5.2(P1) applied to the extended branch, whenever the indicator set Ej∗\mathcal{E}_{j^\ast} lies on the same side of Γ\Gamma as τj∗\tau_{j^\ast}. Without a reference stencil, all the active stencils may straddle Γ\Gamma, and no choice of the weights can produce an accurate value: this is what happens near the points where the line geometry of § 6 meets ∂Ω\partial\Omega.

The active stencils subject to (A3) are precisely the straddling ones; under (A1), all the other active stencils lie on the side of xx, so that (A3) is the indicator-separation hypothesis proper: it asks that the indicator detects every active straddling stencil, with a lower bound cBc_B independent of hh, so that the nonlinear weighting damps its contribution by a factor of order (hd+1/cB)t(h^{d+1}/c_B)^t. Lemma 5.2(P2) does not cover this case, since it concerns one-sided stencils whose indicator set crosses Γ\Gamma, and the following configuration shows that the lower bound in (A3) cannot be deduced from Definition 4.1 alone.

Remark 5.6 (an undetected straddling stencil). Let s=2s=2, d=1d=1, and write (u,v)(u,v) for the coordinates in R2\mathbb{R}^2. Let Γ={u=0}\Gamma=\{u=0\} and let f~\tilde{f} be the unit step,

f~(u,v)={0,u<0,1,u≥0.\tilde{f}(u,v)= \begin{cases} 0, & u<0,\\ 1, & u\ge0. \end{cases}

Consider

τj={(−h,0),(h,−h),(h,h)},Ej={(−h,h)}.\tau_j=\{(-h,0),(h,-h),(h,h)\}, \qquad\mathcal{E}_j=\{(-h,h)\}.

The stencil is unisolvent, satisfies Assumption 5.1 uniformly in hh, and straddles Γ\Gamma. Its linear interpolant is

Pj(u,v)=u+h2h.P_j(u,v)=\frac{u+h}{2h}.

Since Pj(−h,h)=0=f~(−h,h)P_j(-h,h)=0=\tilde{f}(-h,h), one has

Ij=0,I_j=0,

although the stencil crosses a jump of size one. Hence, the residual indicator of Definition 4.1 does not, in general, provide a uniform positive lower bound for arbitrary straddling stencils, and the lower bound required in (A3) must be imposed separately.

Finally, (A4) keeps xx uniformly separated, at the scale qXq_X, from the nodes of the straddling stencils. The compact multinode weights are singular at the nodes, and a straddling stencil with a node very close to xx would have an unnormalized weight large enough to compensate the damping produced by (A3); (A4) bounds this weight in terms of qXq_X, and it is used only in the weight comparison of the proof.

Theorem 5.7 (behaviour near the discontinuity). Let Assumptions 5.1 and 5.5 hold, let 0<ϵ≤hd+10<\epsilon\le h^{d+1}, and let t≥1t\ge1 be fixed. Then, for all sufficiently small hh,

∣f~(x)−K~[f~](x)∣≤K1hd+1+K2h(d+1)t,\left|\tilde{f}(x)-\widetilde{K}[\tilde{f}](x)\right| \le K_1h^{d+1}+K_2h^{(d+1)t},

where

K1=C(s,d,c1,cE,σ0)max⁡{∣f1∣d+1,∣f2∣d+1},K_1=C(s,d,c_1,c_E,\sigma_0)\max\{|f_1|_{d+1},|f_2|_{d+1}\},

and

K2=Nact(c2CqXγθ)μm(1+CGcB)t(1+Λ)∥f~∥∞.K_2=N_{\mathrm{act}}\left(\frac{c_2Cq_X}{\gamma\theta}\right)^{\mu m} \left(\frac{1+C_G}{c_B}\right)^t (1+\Lambda)\|\tilde{f}\|_\infty.

Here NactN_{\mathrm{act}} is an hh-independent upper bound on ∣Jx∣|J_x|, established in the proof. In particular, for every fixed t≥1t \ge1,

∣f~(x)−K~[f~](x)∣=O(hd+1).\left|\widetilde{f}(x)-\widetilde{K}[\widetilde{f}](x)\right|=O(h^{d+1}).

The constants are independent of hh and ϵ\epsilon; their dependence on the remaining parameters is displayed above, together with the dependence on the Cd+1C^{d+1} seminorms of the extended branches.

Proof. Let G\mathcal{G} denote the set of one-sided active stencils and set

B:=Jx∖G.\mathcal{B}:=J_x\setminus\mathcal{G}.

By (A1), all stencils in G\mathcal{G} lie on the same side of Γ\Gamma as xx, while every stencil in B\mathcal{B} is not one-sided. Without loss of generality, let x∈Ω+x\in\Omega^+.

We first show that the number of active stencils is bounded independently of hh. If j∈Jxj\in J_x, then x∈int⁡(Cj)x\in\operatorname{int}(C_j) and therefore, by the definition of CjC_j,

∥x−xji∥<Rj≤c2h,i=1,…,m.\lVert x-x_{j_i}\rVert<R_j\le c_2h,\qquad i=1,\ldots,m.

Hence all the nodes of every active stencil belong to B(x,c2h)B(x,c_2h). The open balls B(xi,qX)B(x_i,q_X) centered at the data sites in X∩B(x,c2h)X\cap B(x,c_2h) are pairwise disjoint and are contained in B(x,c2h+qX)B(x,c_2h+q_X). Comparing volumes and using h≤cquqXh\le c_{\mathrm{qu}}q_X gives

∣X∩B(x,c2h)∣≤(c2h+qXqX)s≤(1+c2cqu)s=:κ.|X\cap B(x,c_2h)|\le\left(\frac{c_2h+q_X}{q_X}\right)^s\le(1+c_2c_{\mathrm{qu}})^s=:\kappa.

Since Sd\mathcal{S}_d consists of pairwise distinct mm-subsets of XX, it follows that

∣Jx∣≤(⌈κ⌉m)=:Nact,|J_x|\le\binom{\lceil\kappa\rceil}{m}=:N_{\mathrm{act}},

which is independent of hh. Distinctness is essential here: allowing repeated copies of a straddling stencil would let their total normalized weight remain O(1)O(1), however strong the damping of each copy. In practice, the minimal-covering construction keeps ∣Jx∣|J_x| much smaller than this crude bound.

We next estimate the contribution of the one-sided stencils. For j∈Gj\in\mathcal{G}, one has τj⊂Ω+\tau_j\subset\Omega^+ and therefore

Pj[f~]=Pj[f1].P_j[\widetilde{f}]=P_j[f_1].

Moreover, since jj is active, (13) gives x∈B‾(aj,c2h)x\in\overline{B}(a_j,c_2h). Hence, by (14),

∣f~(x)−Pj[f~](x)∣≤Chd+1∣f1∣d+1,j∈G.\left|\widetilde{f}(x)-P_j[\widetilde{f}](x)\right|\le Ch^{d+1}|f_1|_{d+1},\qquad j\in\mathcal{G}.

We now bound the normalized weights of the stencils in B\mathcal{B}. By (A2), the reference stencil j∗j^* satisfies

∥x−xji∗∥≤(1−θ)Rj∗,i=1,…,m,\lVert x-x_{j_i^*}\rVert\le(1-\theta)R_{j^*},\qquad i=1,\ldots,m,

and therefore βμ,j∗[f~](x)>0\beta_{\mu,j^*}[\widetilde{f}](x)>0. Thus, for j∈Bj\in\mathcal{B},

B~μ,j[f~](x)≤βμ,j[f~](x)βμ,j∗[f~](x)=W~μ,ju(x)W~μ,j∗u(x)(ϵ+Ij∗ϵ+Ij)t,\widetilde{B}_{\mu,j}[\widetilde{f}](x)\le\frac{\beta_{\mu,j}[\widetilde{f}](x)}{\beta_{\mu,j^*}[\widetilde{f}](x)} =\frac{\widetilde{W}^{u}_{\mu,j}(x)}{\widetilde{W}^{u}_{\mu,j^*}(x)} \left(\frac{\epsilon+I_{j^*}}{\epsilon+I_j}\right)^t,

where W~μ,ju\widetilde{W}^{u}_{\mu,j} denotes the unnormalized numerator in (7). For j∈Bj \in\mathcal{B}, each factor satisfies

(1∥x−xj∗∥−1Rj+)μ≤∥x−xj∥−μ.\left(\frac{1}{\lVert x-x_{j_*}\rVert}-\frac{1}{R_{j}+}\right)^{\mu}\leq\lVert x-x_{j}\rVert^{-\mu}.

By (A4) and h≤cquQXh\leq c_{qu}QX,

∥x−xj∥−μ≤(γ0qX)−μ≤(cquγ0)μh−μ,\lVert x-x_{j}\rVert^{-\mu}\leq(\gamma_{0}qX)^{-\mu}\leq\left(\frac{c_{qu}}{\gamma_{0}}\right)^{\mu}h^{-\mu},

and consequently

W~μ,ju(x)≤(cquγ0)μmh−μm.\widetilde{W}_{\mu,j}^{u}(x)\leq\left(\frac{c_{qu}}{\gamma_{0}}\right)^{\mu m}h^{-\mu m}.

On the other hand, setting

ηj:=∥x−xj∗∥,\eta_{j}:=\lVert x-x_{j_*}\rVert,

condition (A2) gives

ηj≤(1−θ)Rj∗,\eta_{j}\leq(1-\theta)R_{j_*},

and hence

1ηj−1Rj∗=Rj∗−ηjηjRj∗≥θRj∗≥θc2h.\frac{1}{\eta_{j}}-\frac{1}{R_{j_*}}=\frac{R_{j_*}-\eta_{j}}{\eta_{j}R_{j_*}}\geq\frac{\theta}{R_{j_*}}\geq\frac{\theta}{c_{2}h}.

Therefore,

W~μ,j∗u(x)≥(θc2)μmh−μm,\widetilde{W}_{\mu,j_*}^{u}(x)\geq\left(\frac{\theta}{c_{2}}\right)^{\mu m}h^{-\mu m},

and thus

W~μ,ju(x)W~μ,j∗u(x)≤(c2cquγ0θ)μm.\frac{\widetilde{W}_{\mu,j}^{u}(x)}{\widetilde{W}_{\mu,j_*}^{u}(x)}\leq\left(\frac{c_{2}c_{qu}}{\gamma_{0}\theta}\right)^{\mu m}.

Finally, using ϵ≤hd+1\epsilon\leq h^{d+1}, Ij∗≤CGhd+1I_{j_*}\leq C_{G}h^{d+1} from (A2), and Ij≥cBI_{j}\geq c_{B} from (A3), we obtain

B~μ,j[f~](x)≤(c2cquγ0θ)μm(1+CGcB)th(d+1)t,j∈B.\widetilde{B}_{\mu,j}[\widetilde{f}](x)\leq\left(\frac{c_{2}c_{qu}}{\gamma_{0}\theta}\right)^{\mu m}\left(\frac{1+C_{G}}{c_{B}}\right)^{t}h^{(d+1)t},\qquad j\in\mathcal{B}.

The estimate follows by combining the three bounds. Using the partition of unity,

∣f~(x)−K~[f~](x)∣≤∑j∈GB~μ,j[f~](x)∣f~(x)−Pj[f~](x)∣+∑j∈BB~μ,j[f~](x)∣f~(x)−Pj[f~](x)∣.\begin{aligned} \left|\widetilde{f}(x)-\widetilde{K}[\widetilde{f}](x)\right|\leq\sum_{j\in\mathcal{G}}\widetilde{B}_{\mu,j}[\widetilde{f}](x)\left|\widetilde{f}(x)-P_{j}[\widetilde{f}](x)\right| \\ &+\sum_{j\in\mathcal{B}}\widetilde{B}_{\mu,j}[\widetilde{f}](x)\left|\widetilde{f}(x)-P_{j}[\widetilde{f}](x)\right|. \end{aligned}

By the estimate on the one-sided stencils and the normalization of the nonlinear weights, the first sum is bounded by

Chd+1∣f1∣d+1.C h^{d+1}|f_{1}|_{d+1}.

Furthermore, the uniform bound on the local Lebesgue constants gives

∣Pj[f~](x)∣≤Λ∥f~∥∞,\left|P_{j}[\widetilde{f}](x)\right|\leq\Lambda\lVert\widetilde{f}\rVert_{\infty},

and hence

∣f~(x)−Pj[f~](x)∣≤(1+Λ)∥f~∥∞,j∈B.\left|\widetilde{f}(x)-P_{j}[\widetilde{f}](x)\right|\leq(1+\Lambda)\lVert\widetilde{f}\rVert_{\infty},\qquad j\in\mathcal{B}.

Using the bound on ∣Jx∣|J_{x}| and the bound on the weights of the stencils in B\mathcal{B}, the second sum is therefore bounded by

Nact(c2cquγ0θ)μm(1+CGcB)t(1+Λ)∥f~∥∞h(d+1)t.N_{\mathrm{act}}\left(\frac{c_{2}c_{qu}}{\gamma_{0}\theta}\right)^{\mu m}\left(\frac{1+C_{G}}{c_{B}}\right)^{t}(1+\Lambda)\lVert\widetilde{f}\rVert_{\infty}h^{(d+1)t}.

This proves the stated estimate. The case x∈Ω−x\in\Omega^{-} is analogous. ∎

Remark 5.8 (scope of the theorem). Theorem 5.7 is a pointwise conditional result: the O(hd+1)O(h^{d+1}) rate holds at every evaluation point xx satisfying Assumption 5.5. No uniform validity of (A1)–(A4) with respect to xx is assumed here. Obtaining the rate at every point at distance larger than a fixed multiple of hh from Γ\Gamma would require a covering-regularity property of the selected stencil family, namely the existence, near every such point, of a one-sided reference stencil as in (A2), together with (A1), (A3) and (A4). Establishing such a property for the minimal-covering construction used in the implementation is an open problem; the experiments of Section 6 are consistent with it for Halton nodes and the circular discontinuity. Denoting by HH the computable upper bound of hX,Ωh_{X,\Omega} used in the experiments, see (17) in Section 6, at the four levels of Table 1 the error of the nonlinear operator at distance larger than 2H2H from Γ\Gamma is at most 1.2 times its maximum error in the smooth case, and the band where its error exceeds a quarter of the jump has width between 0.6H0.6H and 0.8H0.8H (Table 4). The replacement of ill-conditioned stencils described after Assumption 5.1 also changes the nodes removed during the covering construction, and hence the subsequent stencils: the covering near Γ\Gamma is sensitive to local choices, which is a further reason why its regularity cannot be taken for granted. We note that, if all the active stencils at a given point xx are one-sided and belong to the same branch as xx, the argument of Theorem 5.4 applies directly and conditions (A3)–(A4) are not needed.

Choice of the exponent tt. Under the condition 0<ϵ≤hd+10 < \epsilon\le h^{d+1}, any fixed t≥1t \ge1 gives the order O(hd+1)O(h^{d+1}) in Theorem 5.7. The estimate, however, does not provide an optimal choice of tt at finite resolution. Indeed, the constant K2K_2 contains the factor

(c2cquγ0θ)μm,\left(\frac{c_2 c_q u}{\gamma_0\theta}\right)^{\mu m},

whereas the contribution of the detected stencils contains

(1+CGcB)th(d+1)t.\left(\frac{1+C_G}{c_B}\right)^t h^{(d+1)t}.

Since the constants involved are not known a priori, these estimates give only qualitative indications on the choice of tt. The second factor decays faster as dd grows, while the first one grows with m=(d+ss)m = \binom{d+s}{s}; at finite resolution this suggests that larger values of tt may be needed at higher degrees to compensate for the larger geometric prefactor. In the numerical experiments we use t=4,6,8,12t = 4, 6, 8, 12 for d=1,2,3,4d = 1, 2, 3, 4, respectively. The sensitivity study of Section 6 shows that, among the values tested, t=6t = 6 gives the smallest error for d=2d = 2, while for d=4d = 4 the error decreases up to t=12t = 12 and remains essentially unchanged for t=14t = 14 and t=16t = 16.

Remark 5.9 (comparison with the degree-zero case). For d=0d = 0, the local interpolants are constants and the construction reduces to a compactly supported WENO–Shepard-type method. Theorems 5.4 and 5.7 then give a first-order approximation rate, as in [13]. The two methods use different smoothness indicators: in [13] the indicator is obtained from an auxiliary least-squares fit, whereas here it is defined through the residuals in Definition 4.1.

For d≥1d \ge1, the use of local polynomial interpolants gives the order O(hd+1)O(h^{d+1}) in smooth regions, and Theorem 5.7 shows that the same order is preserved at points satisfying Assumption 5.5. In the experiments of Section 6 with the circular discontinuity, at the four levels of Table 1 and for every degree, the error of the nonlinear operator at distance larger than 2H2H from Γ\Gamma does not exceed 1.2 times its maximum error in the smooth case: high order and sharp resolution of the discontinuity are obtained simultaneously. The linear and nonlinear compact multinode operators are both convex combinations of the active local interpolants; the difference is that the nonlinear weights reduce the contribution of the stencils detected as non-smooth.

Numerical experiments

All the experiments are performed on Ω=(0,1)2\Omega= (0,1)^2, with NN nodes (N=nN = n in the notation of Section 2), μ=4\mu= 4 and ϵ=10−14\epsilon= 10^{-14}; points of R2\mathbb{R}^2 are written as (x,y)(x,y) in this section. Note that ϵ≤hd+1\epsilon\le h^{d+1} holds throughout the reported resolutions: since NN balls of radius hh cover [0,1]2[0,1]^2, one has h≥(Nπ)−1/2h \ge(N\pi)^{-1/2}, which at the finest level (N=16641N = 16641) gives h≥4.37⋅10−3h \ge4.37 \cdot10^{-3} and h5≥(Nπ)−5/2>1.6⋅10−12>10−14h^5 \ge(N\pi)^{-5/2} > 1.6 \cdot10^{-12} > 10^{-14}, consistently with the theory. Two node distributions are used: Halton points and regular grids with the same number NL=(2l+1)2N_L = (2^l + 1)^2 of nodes. The grid nodes on the boundary of [0,1]2[0,1]^2 do not belong to Ω\Omega; the definitions and results of § 2–§ 5 remain valid, with the same proofs, for X⊂Ω‾X \subset\overline{\Omega}, which is the setting used for the grids, provided that ff and, in § 5, γ\gamma, the sets Ω±\Omega^{\pm} and the branches f1,f2f_1,f_2 are understood as defined on Ω‾\overline{\Omega}, so that the data at the boundary nodes and their assignment to a branch are well defined. The stencils are selected by the discrete Leja-type procedure described in § 5 (LU with row pivoting on the local Vandermonde matrix in a translated and scaled monomial basis [19]); stencils violating σmin⁡(Vj)≥σ0=0.05\sigma_{\min}(V_j) \ge\sigma_0 = 0.05 are replaced along the nested Leja sequence as described in § 5. On Halton nodes this happens only at the two finest levels (at most 54 stencils, for d=4d = 4 and l=7l = 7), on regular grids, where nearly collinear configurations are more frequent, only for d≥3d \ge3 (at most 164 stencils, for d=4d = 4 and l=7l = 7), and no stencil remained below σ0\sigma_0 in any experiment. In accordance with § 3, the parameter hh is the certified computable upper bound

hX,Ω≤H:=max⁡z∈Gδmin⁡xi∈X∥z−xi∥+δG,(17)h_{X,\Omega} \le H := \max_{z \in G_{\delta}} \min_{x_i \in X} \lVert z-x_i\rVert+ \delta_G, \tag*{(17)}

where GδG_{\delta} is an auxiliary uniform grid of covering radius δG\delta_G (in the implementation, δG=δ/2\delta_G = \delta/\sqrt{2} with δ=1/(4N)\delta= 1/(4\sqrt{N}) the grid spacing, and the grid covers the convex hull of XX enlarged by δG\delta_G); since this set does not contain the whole of Ω\Omega, we also evaluated the same bound on a finer grid, of spacing δ/4\delta/4, covering [0,1]2[0,1]^2, obtaining 0.0781, 0.0407 and 0.0226 for N=289N = 289, 1089 and 4225, all smaller than the corresponding values of HH in Table 1 (for N=16641N = 16641 the bound is 0.0119, against H=0.0129H = 0.0129); on the regular grids HH exceeds the exact fill distance 2−l/22^{-l}/\sqrt{2} at every level, so that H>hX,ΩH > h_{X,\Omega} holds in every experiment. The strict inequality required by Lemma 3.2 is therefore certified at every level, and no uncovered evaluation point occurred in any experiment. The weights are evaluated in logarithmic form with an incremental log-sum-exp normalization, stable up to the data sites, where the interpolation value is assigned directly. The smoothness indicators are computed on the sets Ej=Ni∖τj\mathcal{E}_j = \mathcal{N}_i \setminus\tau_j introduced after Definition 4.1, and the exponents are paired with the degree as d=1,2,3,4↔t=4,6,8,12d = 1,2,3,4 \leftrightarrow t = 4,6,8,12 (§ 5.4). In tables and captions the data-dependent (nonlinear) CMS is labelled WENO, and the CMS of § 3 linear. As reference smooth datum we use Franke’s function

Table 1: Smooth Franke data, Halton nodes: errors and rates for the linear CMS and the data-dependent (WENO) CMS, local degrees d=1,…,4d = 1,\ldots,4 with exponents t=4,6,8,12t = 4,6,8,12.

ddllNNHHE∞linE_{\infty}^{\mathrm{lin}}p∞p^{\infty}E∞WENOE_{\infty}^{\mathrm{WENO}}p∞p^{\infty}RMSEWENO\mathrm{RMSE}^{\mathrm{WENO}}p2p^{2}
142890.08796.168e-02–5.568e-02–9.343e-03–
510890.04212.709e-021.122.702e-020.982.937e-031.57
642250.02466.255e-032.726.174e-032.747.152e-042.62
7166410.01292.469e-031.452.810e-031.231.964e-042.02
242890.08793.749e-02–3.922e-02–4.652e-03–
510890.04211.153e-021.607.933e-032.177.282e-042.52
642250.02461.028e-034.488.636e-044.119.947e-053.69
7166410.01293.563e-041.651.578e-042.651.344e-053.12
342890.08793.692e-02–2.489e-02–2.452e-03–
510890.04215.135e-032.683.783e-032.562.925e-042.89
642250.02462.801e-045.402.352e-045.151.873e-055.10
7166410.01293.280e-053.352.455e-053.531.453e-063.99
442890.08794.490e-02–4.274e-02–1.747e-03–
510890.04212.055e-034.192.056e-034.139.419e-053.97
642250.02468.994e-055.819.274e-055.754.092e-065.82
7166410.01293.477e-065.082.678e-065.531.458e-075.20

Table 1.

f(x,y)=34e−14((9x−2)2+(9y−2)2)+34e−149(9x+1)2−110(9y+1)2+12e−14((9x−7)2+(9y−3)2)−15e−(9x−4)2−(9y−7)2.(18)f(x,y) = \frac{3}{4}e^{-\frac{1}{4}((9x-2)^2+(9y-2)^2)} + \frac{3}{4}e^{-\frac{1}{49}(9x+1)^2-\frac{1}{10}(9y+1)^2} + \frac{1}{2}e^{-\frac{1}{4}((9x-7)^2+(9y-3)^2)} - \frac{1}{5}e^{-(9x-4)^2-(9y-7)^2}. \tag*{(18)}

The errors of an approximant I\mathcal{I} (I=M~μ\mathcal{I} = \widetilde{M}_{\mu} for the linear operator, I=K~\mathcal{I} = \widetilde{K} for the nonlinear one) are measured on a uniform evaluation grid of Neval=1002N_{\mathrm{eval}} = 100^2 points ziz_i as the maximum error and the root mean square error

E∞=max⁡i∣f(zi)−I(zi)∣,RMSE=(1Neval∑i(f(zi)−I(zi))2)1/2,E_{\infty} = \max_i \lvert f(z_i)-\mathcal{I}(z_i)\rvert,\qquad\mathrm{RMSE} = \left(\frac{1}{N_{\mathrm{eval}}}\sum_i(f(z_i)-\mathcal{I}(z_i))^2\right)^{1/2},

with rates pl∞=log⁡(E∞(l−1)/E∞(l))/log⁡(Hl−1/Hl)p_l^{\infty} = \log(E_{\infty}^{(l-1)}/E_{\infty}^{(l)})/\log(H_{l-1}/H_l), where E∞(l)E_{\infty}^{(l)} and HlH_l are the values of E∞E_{\infty} and HH at level ll, and analogously pl2p_l^2, computed with unrounded values of HH. (The quantity E∞E_{\infty} is called maximum absolute error, MAE, in [13]; we prefer the unambiguous notation.)

Order of accuracy in smooth regions

We approximate (18) from Nl=(2l+1)2N_l = (2^l+1)^2 Halton nodes and regular grid nodes, l=4,5,6,7l = 4,5,6,7, for local degrees d=1,…,4d = 1,\ldots,4. Table 1 reports the results for the Halton nodes, Table 2 those for the regular grids. The linear and the nonlinear operators exhibit the same convergence orders at every degree, in accordance with Theorem 5.4. The root mean square errors are consistent with the order d+1d+1 (rates 2.02, 3.12, 3.99 and 5.20 at the finest step for the nonlinear operator, after values above d+1d+1 at the previous step); least squares slopes over the four levels 2.05, 3.09, 3.95 and 4.95), whereas the maximum-norm rates oscillate between consecutive levels, e.g. 1.12, 2.72, 1.45 for d=1d = 1. On scattered nodes the stencils, and hence the local constants in (14), change from one level to the next; the oscillation of the maximum-norm rates is consistent with this variation rather than with a loss of order, as the least squares slopes of the root mean square errors and the results on the regular grids indicate. On the regular grids the maximum-norm rates of the linear operator do not show the oscillations observed on the Halton set: they stay between 2.02 and 2.04 for d=1d = 1 and increase monotonically for d≥2d \ge2, and at the finest step they are 2.04, 3.10, 3.93 and 5.24; those of the nonlinear operator show small oscillations for d=3d = 3; at equal number of nodes the maximum errors on the grids are smaller than on the Halton set for d=1d = 1 and d=4d = 4 at every level, but not for d=2d = 2 and d=3d = 3: the grid error is the larger one at d=2d = 2, l=4,6l = 4,6 and d=3d = 3, l=5,6l = 5,6 for the linear operator, and at d=2d = 2, l=4,5,6l = 4,5,6 and at every level for d=3d = 3 for the nonlinear one. At the finest level, on the Halton set and for the linear operator, the maximum error decreases by nearly three orders of magnitude (a factor ≈710\approx710) from d=1d = 1 to d=4d = 4 at equal number of nodes.

Table 2: Smooth Franke data, regular grid nodes: errors and rates for the linear CMS and the data-dependent (WENO) CMS, local degrees d=1,…,4d=1,\ldots,4 with exponents t=4,6,8,12t=4,6,8,12.

ddllNNHHE∞linE_{\infty}^{\mathrm{lin}}p∞p^{\infty}E∞WENOE_{\infty}^{\mathrm{WENO}}p∞p^{\infty}RMSEWENO\mathrm{RMSE}^{\mathrm{WENO}}p2p^{2}
142890.05202.865e-02–2.864e-02–5.144e-03–
510890.02687.439e-032.037.443e-032.031.275e-032.10
642250.01361.897e-032.021.897e-032.023.188e-042.05
7166410.00694.672e-042.044.674e-042.047.951e-052.03
242890.05204.305e-02–4.534e-02–8.062e-03–
510890.02687.890e-032.568.081e-032.601.127e-032.97
642250.01361.113e-032.891.160e-032.861.436e-043.04
7166410.00691.333e-043.101.344e-043.141.850e-052.99
342890.05202.448e-02–2.612e-02–3.884e-03–
510890.02685.446e-032.274.385e-032.693.209e-043.76
642250.01364.829e-043.573.166e-043.882.386e-053.83
7166410.00693.260e-053.933.259e-053.321.535e-064.00
442890.05202.085e-02–2.085e-02–2.822e-03–
510890.02681.711e-033.771.692e-033.791.298e-044.64
642250.01366.545e-054.816.551e-054.804.977e-064.81
7166410.00691.799e-065.241.838e-065.211.603e-075.01

Table 2.

Approximation of piecewise smooth functions

We consider the piecewise smooth datum f~(x,y)=f(x,y)+χΩ+(x,y)\tilde{f}(x,y) = f(x,y) + \chi_{\Omega^{+}}(x,y), with χΩ+\chi_{\Omega^{+}} the characteristic function of Ω+\Omega^{+} and ff as in (18) and Ω+\Omega^{+} the disk of radius 0.25 centered at (12,12)\left(\frac{1}{2},\frac{1}{2}\right), sampled at N=652N = 652 Halton nodes (H=0.0246H = 0.0246). Figure 1 compares the original datum with the linear and the nonlinear reconstructions for d=1d = 1; Figure 2 shows the corresponding error maps in logarithmic scale, and Figure 3 a one-dimensional section together with the empirical distribution of the smoothness indicators.

Top views: original datum $\tilde{f}$ (left), linear CMS (center), data-dependent CMS (right)

Figure 1. Top views: original datum f~\tilde{f} (left), linear CMS (center), data-dependent CMS (right); circle geometry, Halton nodes, N=652N = 652, d=1d = 1.

Log10 absolute error of the linear and data-dependent CMS

Figure 2. log⁡10\log_{10} absolute error of the linear (left) and data-dependent (right) CMS; the dashed curve is Γ\Gamma. Same data as Figure 1.

Section along $y = 0.5$ and histogram of $\log_{10} I_j$

Figure 3. Left: section along y=0.5y = 0.5. Right: histogram of log⁡10Ij\log_{10} I_j; the dashed line marks H2H^2. Out of 2179 stencils, the 65 whose nodes straddle Γ\Gamma have indicators larger than 0.18; together with 36 one-sided stencils near Γ\Gamma, detected through their indicator sets as in Lemma 5.2(P2), they form the upper mode of the distribution, 101 stencils with Ij>0.17I_j > 0.17 (median 0.50). All the other indicators are at most 1.35×10−21.35 \times10^{-2}, so that no indicator lies between 1.35×10−21.35 \times10^{-2} and 0.17; the two modes of the distribution are separated by about three orders of magnitude.

Table 3 quantifies the comparison for d=1,…,4d = 1,\ldots,4. Three effects are apparent. First, the error of the nonlinear operator at distance >H> H from Γ\Gamma decreases with the degree, within a factor of four of the smooth case at distance >H> H and at the level of the smooth case at distance >2H> 2H, while the linear operator error remains between 0.25 and 1.2 there at the tested resolution. Second, the width of the contaminated band (points with error larger than a quarter of the jump) for the linear operator grows with the degree (1.3H1.3H, 1.8H1.8H, 2.0H2.0H, 2.7H2.7H), while it remains within 0.70.7–0.8H0.8H for the nonlinear one. The band width is the largest distance from Γ\Gamma of an evaluation point at which the error exceeds a quarter of the jump; it is measured on a locally refined set of evaluation points within 4H4H of Γ\Gamma, with spacing H/10H/10 in the normal direction and about H/5H/5 or less along Γ\Gamma. Third, the deviations of the linear operator beyond the range of f~\tilde{f} on the evaluation grid remain substantial at all degrees, both above the maximum (up to +0.686) and below the minimum (up to 0.954), while for the nonlinear operator they are at most 2.4⋅10−22.4\cdot10^{-2} above the maximum and 4.0⋅10−34.0\cdot10^{-3} below the minimum.

Table 3: Jump on the circle, Halton nodes, N=652N=65^{2}, H=0.0246H=0.0246: maximum errors at distance >H>H and >2H>2H from Γ\Gamma, width of the band where the error exceeds one quarter of the jump (measured on a locally refined set near Γ\Gamma), signed maximal deviation max⁡I~−max⁡f~\max\widetilde{I}-\max\widetilde{f} (positive values are overshoots; negative values indicate that the reconstruction stays below the maximum of f~\widetilde{f}), and undershoot (min⁡f~−min⁡I)+(\min\widetilde{f}-\min I)_{+}; maxima and minima are taken over the evaluation grid.

dd (tt)methodE∞E_{\infty} (>H>H)E∞E_{\infty} (>2H>2H)banddeviationundershoot
1 (4)linear3.344e-016.255e-031.3HH+5.79e-012.55e-01
WENO7.280e-036.174e-030.7HH−8.82e-044.00e-03
2 (6)linear2.545e-013.172e-021.8HH+2.71e-011.84e-01
WENO1.665e-038.619e-040.8HH+3.95e-040
3 (8)linear1.150e+002.334e-012.0HH+3.99e-019.19e-01
WENO5.096e-042.352e-040.8HH+2.38e-020
4 (12)linear7.318e-015.577e-012.7HH+6.86e-019.54e-01
WENO3.656e-049.274e-050.8HH−6.51e-030

Table 3.

To check that the width of the contaminated band is proportional to hh, we repeat the experiment on the four levels l=4,…,7l = 4,\ldots,7 of Table 1. Table 4 reports the band widths, measured on the refined set, in units of HH: for the nonlinear operator they remain between 0.6H0.6H and 0.8H0.8H at every level and degree, so that, over the tested levels, the band shrinks proportionally to HH; for the linear operator they remain between 1.2H1.2H and 2.9H2.9H. At the same four levels and for every degree, the maximum error of the nonlinear operator at distance larger than 2H2H from Γ\Gamma does not exceed its maximum error on the smooth datum (Table 1), with the only exception of d=3d=3, l=5l=5, where it is 1.2 times as large; at distance larger than HH the ratio between the two errors is at most 4, except for d=3d=3, l=5l=5, where it is about 16.

dd (tt)methodl=4l = 4 H=0.0879H = 0.0879l=5l = 5 H=0.0421H = 0.0421l=6l = 6 H=0.0246H = 0.0246l=7l = 7 H=0.0129H = 0.0129
1 (4)linear1.21.61.31.3
1 (4)WENO0.70.70.70.7
2 (6)linear1.62.11.81.8
2 (6)WENO0.60.70.80.6
3 (8)linear1.52.92.02.3
3 (8)WENO0.70.80.80.8
4 (12)linear2.52.42.72.1
4 (12)WENO0.60.80.80.7

Table 4. Jump on the circle, Halton nodes, N=(2l+1)2N = (2l + 1)^2: width of the band where the error exceeds one quarter of the jump, in units of HH, for the linear and the data-dependent (WENO) CMS (measured as in Table 3).

To assess the dependence on the geometry of Γ\Gamma, we repeat the experiment with Ω+={x+y≤1}\Omega^{+}=\{x+y\leq1\}, whose boundary Γ\Gamma is a line crossing ∂Ω\partial\Omega, and with Ω+=[12,1]2\Omega^{+}=[\frac{1}{2},1]^{2}, a square with a corner at (12,12)(\frac{1}{2},\frac{1}{2}) whose sides meet ∂Ω\partial\Omega, using the same nodes and parameters; the results are reported in Table 5. The corner of the square lies outside the C1C^{1} setting of Section 5, so that this geometry serves as a stress test. At distance greater than 2H2H from Γ\Gamma the nonlinear operator recovers, for both geometries and every degree, the accuracy of the smooth case: the errors do not exceed the maximum errors of Table 1 at l=6l=6. The linear operator, in contrast, has errors comparable to the jump at distance greater than HH in all cases and, for the line with d≥2d\geq2, also beyond 2H2H. Between HH and 2H2H the nonlinear operator is less robust than for the circle. Errors larger than a quarter of the jump occur for the line with d=2d=2 and for the square with d=3d=3 and d=4d=4, at no more than two evaluation points in each case, all at distance between HH and 1.5H1.5H from Γ\Gamma; for the line with d=3d=3 and d=4d=4 the error at distance >H>H remains below a quarter of the jump but well above the smooth level, while for the square with d=2d = 2 there is no deterioration. The inspection of the active stencils at these points shows that they are precisely configurations excluded by Assumption 5.5. Near the points where the line meets ∂Ω\partial\Omega, only stencils straddling Γ\Gamma are active, so that (A2) fails. Near the corner of the square and near the points where its sides meet ∂Ω\partial\Omega, a one-sided stencil of the opposite branch is active and, its indicator being small, receives a large weight, so that (A1) fails, as anticipated in the comment following Assumption 5.5. In all these cases the straddling stencils are detected by the indicator (Ij≥2.6⋅10−2I_j \ge2.6 \cdot10^{-2}): the failures are due to the covering and not to the detection mechanism, in accordance with Remark 5.8.

dd (tt)method\multicolumn{3}{c}{line}\multicolumn{3}{c}{square}
E∞E_\infty (>H> H)E∞E_\infty (>2H> 2H)bandE∞E_\infty (>H> H)E∞E_\infty (>2H> 2H)band
1 (4)linear4.345e-016.255e-031.5H1.5H4.493e-016.255e-031.4H1.4H
WENO6.174e-036.174e-030.6H0.6H6.174e-036.174e-030.5H0.5H
2 (6)linear1.026e+001.026e+002.0H2.0H2.854e-019.474e-041.0H1.0H
WENO4.000e-018.636e-041.4H1.4H9.541e-048.619e-040.8H0.8H
3 (8)linear1.437e+001.437e+002.1H2.1H7.482e-017.912e-021.7H1.7H
WENO5.555e-022.352e-040.8H0.8H1.000e+002.352e-041.1H1.1H
4 (12)linear2.183e+004.095e-012.2H2.2H6.035e-012.345e-012.5H2.5H
WENO1.380e-019.274e-051.0H1.0H3.528e-019.274e-051.0H1.0H

Table 5. Jump along a line (Ω+={x+y≤1}\Omega^+ = \{x + y \le1\}) and along the sides of a square (Ω+=[12,1]2\Omega^+ = [\frac{1}{2},1]^2), Halton nodes, N=652N = 65^2, H=0.0246H = 0.0246: maximum errors at distance >H> H and >2H> 2H from Γ\Gamma and width of the band where the error exceeds one quarter of the jump (measured as in Table 3; for the linear operator on the square with d=2d = 2, the 1002100^2 evaluation grid contains a point above the threshold at distance 1.4H1.4H from Γ\Gamma, not captured by the refined set).

Finally, we compare the Halton set with a regular grid of the same cardinality. Distances from Γ\Gamma and band widths have so far been expressed in units of HH. For a fixed number of nodes, however, HH depends on the uniformity of the node distribution, whereas the size of the stencils depends on the node density: for N=652N = 652, HH is about 1.6 times the mean node spacing on the Halton set and about 0.87 times the spacing on the regular grid. Thresholds in units of HH are therefore not comparable across node distributions, and we measure the errors of the nonlinear operator at the same physical distances δH\delta_H, 2δH2\delta_H and 3δH3\delta_H from Γ\Gamma, with δH=0.0246\delta_H = 0.0246 the value of HH for the Halton set, for the three geometries of this section (Table 6). For d≤3d \le3 the two node distributions behave comparably: at distance larger than 2δH2\delta_H the regular grid yields, for every geometry, errors comparable to those of the smooth case (Table 2, l=6l = 6). For d=4d = 4 the contaminated band on the grid is wider: errors of order 10−210^{-2} persist up to 2δH2\delta_H for all three geometries, and the smooth level is reached only at distance 3δH3\delta_H; closer to Γ\Gamma, for the circle, isolated values exceed the jump, with errors up to about 4 at distance between the grid value of HH and δH\delta_H. At distance larger than δH\delta_H the grid is more accurate than the Halton set for d=1d = 1 and in some cases with d≥2d \ge2 (the line with d=2d = 2 and d=3d = 3, the square with d=3d = 3 and d=4d = 4), and less accurate in the others (the circle with d=2,3,4d = 2, 3, 4, the line with d=4d = 4, the square with d=2d = 2). Two features specific to regular grids should be noted. First, the discrete Leja selection meets exact ties, so that the stencils, and hence the errors closest to Γ\Gamma, depend on the tie-breaking rule of the LU factorization. Second, for the line and the square some nodes lie exactly on Γ\Gamma. Shifting Γ\Gamma by 0.37 grid spacings, so that no node lies on it, reduces the error at distance larger than δH\delta_H for the square with d=3d = 3 from 0.17 to 5.8⋅10−45.8 \cdot10^{-4} and for the square with d=2d = 2 from 3.0⋅10−33.0 \cdot10^{-3} to 9.9⋅10−49.9 \cdot10^{-4}, while it leaves the other cases essentially unchanged. Overall, on regular grids the method performs as on scattered nodes for d≤3d \le3, while for d=4d = 4 the contaminated band is wider.

Γ\GammaddHaltonregular grid
>δH>\delta_H>2δH>2\delta_H>3δH>3\delta_H>δH>\delta_H>2δH>2\delta_H>3δH>3\delta_H
circle17.3e-036.2e-036.2e-031.9e-031.8e-031.8e-03
21.7e-038.6e-048.3e-041.9e-031.2e-031.2e-03
35.1e-042.4e-042.4e-048.2e-042.9e-042.9e-04
43.7e-049.3e-059.3e-059.0e-024.3e-025.2e-05
line16.2e-036.2e-036.2e-031.9e-031.9e-031.9e-03
24.0e-018.6e-048.6e-041.1e-011.2e-031.2e-03
35.6e-022.4e-042.4e-043.9e-023.2e-043.2e-04
41.4e-019.3e-059.3e-052.6e-012.2e-026.6e-05
square16.2e-036.2e-036.2e-031.9e-031.9e-031.8e-03
29.5e-048.6e-048.6e-043.0e-039.9e-049.9e-04
31.0e+002.4e-042.4e-041.7e-013.1e-043.1e-04
43.5e-019.3e-059.3e-051.2e-014.0e-025.2e-05

Table 6. Halton nodes versus regular grid, N=652N = 652: maximum error of the data-dependent CMS at distance larger than δH\delta_H, 2δH2\delta_H and 3δH3\delta_H from Γ\Gamma, with δH=0.0246\delta_H = 0.0246 for both node distributions.

Sensitivity to the exponent tt

Table 7 reports the maximum error at distance >H> H from Γ\Gamma as a function of tt, for d=2d = 2 and d=4d = 4. For d=2d = 2 the choice t=6t = 6 is the best among those tested, with a mild degradation for larger tt. For d=4d = 4 the error decreases monotonically up to t=12t = 12 and then remains at the same level for t=14t = 14 and t=16t = 16, in qualitative agreement with the discussion of the exponent in § 5.4.

t=2t = 2t=4t = 4t=6t = 6t=8t = 8t=10t = 10t=12t = 12t=14t = 14t=16t = 16
d=2d = 25.828e-022.864e-021.665e-032.194e-032.778e-033.014e-03––
d=4d = 45.140e-011.834e-017.677e-025.325e-027.434e-033.656e-043.669e-043.674e-04

Table 7. Sensitivity to tt: maximum error at distance >H> H from Γ\Gamma (circle geometry, Halton nodes, N=652N = 652).

Reproducibility

The experiments were performed with a MATLAB code building on the multinode Shepard implementation [16]; the results were independently verified with a separate Python implementation. The codes, together with the scripts generating every table and figure of this section, are available from the authors.

Conclusions

We have introduced a data-dependent compact multinode Shepard method which combines the approximation order of the multinode construction with the essentially non-oscillatory behaviour of WENO-type weights. The smoothness indicator is provided by the residuals of the local interpolants on nodes outside the stencils, without additional function evaluations, and the nonlinear renormalization preserves the partition of unity, the interpolation property, the guaranteed regularity class and the convex-combination structure of the linear operator. The operator attains the order hd+1h^{d+1} in smooth regions for any choice of the parameters and, under an explicit indicator-separation hypothesis, the same order near a jump discontinuity, with a transparent analysis of the constants: the prefactor of the damped contributions grows exponentially with the stencil cardinality, which may contribute to the finite-resolution need for larger exponents tt at higher degrees. We have also delimited the scope of the detection mechanism by an explicit configuration in which a stencil straddling the discontinuity escapes the basic indicator. The numerical experiments confirm the theory for local degrees up to four, on scattered and on regular grid nodes. For the circular discontinuity on Halton nodes with N=652N = 65^2 the nonlinear operator improves on the linear one, at distance larger than HH from Γ\Gamma, by a factor between 45 and 2.3⋅1032.3 \cdot10^3 (Table 3), with the largest gains at the higher degrees. For the line and square geometries the corresponding gain is irregular in the degree, ranging from a factor of about 300 (square, d=2d = 2) to none (square, d=3d = 3, where the nonlinear operator is the less accurate of the two), and on regular grids the contaminated band is wider for d=4d = 4 (§ 6); for all the geometries and degrees tested on Halton nodes, with the exponents tt of § 5.4, the nonlinear operator recovers the accuracy of the smooth case at distance larger than 2H2H.

The few points at distance larger than HH from Γ\Gamma where the nonlinear operator loses accuracy, on the line and square geometries, are all points where either no one-sided stencil is active or a one-sided stencil of the opposite branch is active (§ 6): the loss is due to the covering, not to the indicator. This, together with the exponential dependence of the constants on the stencil cardinality, points to coverings adapted to the discontinuity, in which straddling stencils are never active and conditions (A1) and (A3) of Assumption 5.5 hold by construction. This is the subject of a forthcoming paper by the authors.

Acknowledgements

The first three authors carried out this research as part of RITA (Research ITalian network on Approximation) and the UMI group “Teoria dell’Approssimazione e Applicazioni”. They have been supported by the GNCS-INdAM 2026 project “Metodi polinomiali e kernel per l’approssimazione da dati discreti e integrali con software OS”. They are also members of the INdAM-GNCS Research Group.

The fourth and fifth authors have been supported through GVA project CIAICO/2024/089, the fifth author has also been funded by grant PID2023-146836NB-I00 funded by MCIN/AEI/10.13039/501100011033 and by ERDF/EU.

References

  1. [1]D. Shepard, A Two-Dimensional Interpolation Function for Irregularly-Spaced Data, in: Proceedings of the 1968 23rd ACM National Conference, 1968, pp. 517–524.DOI
  2. [2]R. Franke, G. M. Nielson, Smooth Interpolation of Large Sets of Scattered Data, Int. J. Numer. Methods Eng. 15 (11) (1980) 1691–1704.
  3. [3]F. Dell’Accio, F. Di Tommaso, Rate of Convergence of Multinode Shepard Operators, Dolomites Res. Notes Approx. 12 (2019) 1–6.
  4. [4]F. Dell’Accio, F. Di Tommaso, On the Hexagonal Shepard Method, Appl. Numer. Math. 150 (2020) 51–64.DOI
  5. [5]F. Dell’Accio, F. Di Tommaso, K. Hormann, On the Approximation Order of Triangular Shepard Interpolation, IMA J. Numer. Anal. 36 (1) (2016) 359–379.DOI
  6. [6]F. Dell’Accio, F. Di Tommaso, R. Lammirato, F. Larosa, Scattered Data Interpolation on the Torus by Compactly Supported Multinode Shepard Operators, arXiv:2609.02259 (2026).arxiv.org/abs/2609.02259
  7. [7]F. Aràndiga, A. Cohen, R. Donat, N. Dyn, Interpolation and Approximation of Piecewise Smooth Functions, SIAM J. Numer. Anal. 43 (2005) 41–57.DOI
  8. [8]M. Bozzini, M. Rossini, The Detection and Recovery of Discontinuity Curves from Scattered Data, J. Comput. Appl. Math. 240 (2013) 148–162.DOI
  9. [9]L. Lenarduzzi, R. Schaback, Kernel-Based Adaptive Approximation of Functions with Discontinuities, Appl. Math. Comput. 307 (2017) 113–123.DOI
  10. [10]C.-W. Shu, High Order Weighted Essentially Nonoscillatory Schemes for Convection Dominated Problems, SIAM Rev. 51 (1) (2009) 82–126.DOI
  11. [11]S. Amat, D. Levin, J. Ruiz-Álvarez, D. F. Yáñez, Non-Linear WENO B-Spline Based Approximation Method, Numer. Algorithms 98 (2025) 1141–1169.arxiv.org/abs/2308.06153
  12. [12]S. Amat, D. Levin, J. Ruiz-Álvarez, D. F. Yáñez, A New B-Spline Type Approximation Method for Non-Smooth Functions, Appl. Math. Lett. 141 (2023) 108628.DOI
  13. [13]D. Levin, J. M. Ramón, J. Ruiz-Álvarez, D. F. Yáñez, Weighted Essentially Non-Oscillatory Shepard Method, Numer. Algorithms 102 (2025) 593–609.arxiv.org/abs/2412.02286
  14. [14]J. M. Ramón, J. Ruiz-Álvarez, D. F. Yáñez, Non-Linear Partition of Unity Method, J. Comput. Appl. Math. 473 (2026) 116891.arxiv.org/abs/2501.09381
  15. [15]D. Levin, J. M. Ramón, J. Ruiz-Álvarez, D. F. Yáñez, Data-Dependent Moving Least Squares, Appl. Numer. Math. 216 (2025) 56–75.arxiv.org/abs/2412.02304
  16. [16]F. Dell’Accio, F. Di Tommaso, F. Larosa, The Multinode Shepard Method: MATLAB Implementation, J. Approx. Softw. 1 (2) (2024).DOI
  17. [17]G. E. Fasshauer, Meshfree Approximation Methods with MATLAB, World Scientific, Singapore, 2007.DOI
  18. [18]R. E. Barnhill, R. P. Dube, F. F. Little, Properties of Shepard’s surfaces, Rocky Mountain J. Math. 13 (1983) 365–382.DOI
  19. [19]L. Bos, S. De Marchi, A. Sommariva, M. Vianello, Computing Multivariate Fekete and Leja Points by Numerical Linear Algebra, SIAM J. Numer. Anal. 48 (2010) 1984–1999.DOI
  20. [20]H. Whitney, Functions Differentiable on the Boundaries of Regions, Ann. Math. 35 (3) (1934) 482–485.
  21. [21]H. Whitney, Analytic Extensions of Differentiable Functions Defined in Closed Sets, Trans. Amer. Math. Soc. 36 (1934) 63–89.

Paper details

vlnc:W_ns5d5cur
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC0-1.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents