Convergence of Planar Curve Interpolation Schemes

Robert Schaback

Abstract This note provides convergence orders for a number of parametric interpolation schemes for planar curves. The methods use piecewise quadratic or cubic polynomials and are globally GC^{1} or GC^{2}. The data are either of Lagrange or of Hermite type; convergence orders range between 4 and 6.

§1. Introduction

Let f : [0, L] → IR^{2} be a smooth planar curve, parametrized by arclength. We consider interpolation processes using data

f_{i} := f(t_{i}), 0 ≤ i ≤ N,  (1)
f′_{i} := f′(t_{i}), 0 ≤ i ≤ N,  (2)
κ_{i} := κ_{f}(t_{i}), 0 ≤ i ≤ N  (3)

at unknown parameter values

0 = t_{0} < t_{1} < … < t_{N} = L,  (4)

where κ_{f} denotes the curvature of f. We employ the notation Hj for values j = 0, 1, 2 to describe the situation of Hermite interpolation of order j; i.e., when equation (i + 1) is required to hold for 0 ≤ i ≤ j ≤ 2.

The interpolants should be piecewise polynomials p of degree k = 2 or k = 3 having breakpoints at the data. The polynomial pieces are written in Bernstein–Bezier (BB) representation as p_{i}(t), 1 ≤ i ≤ N, t ∈ [0, 1], between f(t_{i−1}) and f(t_{i}). Continuity should be of class GC^{l} with l = 1 or l = 2. So the interpolation processes considered here are roughly described by the three numbers j, k, and l.

The error is measured either as in [1] or (equivalently) using the maximum deviation between f and p taken on lines perpendicular to the lines joining adjacent interpolation points f(t_{i−1}) and f(t_{i}).

Approximation Theory VI C. K. Chui, L. L. Schumaker and J. D. Ward (eds.) Copyright, Academic Press, New York, 1989, 1– 4. ISBN 0-12-17585-6: All rights of reproduction in any form reserved.

We consider the limit h → 0, h := max_{1≤i≤N}(t_{i} − t_{i−1}), and derive the order m of the error with respect to h → 0. Table 1 summarizes a number of results for quick reference.

Hj  GC^{l}  ∂p  O(h^{m}) Remarks, references, and
j  l  k  m  additional assumptions
2  2  3  6  if κ_{f} ≠ 0, see [1]
2  2  3  4  if κ_{f} ≥ 0, see [1]
1  1  2  4  if κ_{f} ≠ 0, see 2.1
1  1  3  4  see 2.2
1  2  3  4  see 2.3
1  2  3  6/4 ^{2}) under H2–conditions^{1}), see 3^{3})
0  2  2  4  if κ_{f} ≠ 0, global scheme, see [2]^{3})
0  1  2  4  if κ_{f} ≠ 0, local scheme, see 2.4^{3})
0  1  3  4  see 2.5^{3})
0  2  3  4  see 2.6^{3})
1) under assumptions of the two cases of cubic H2–interpolation
2) the two possible convergence orders

of cubic H2–interpolation

3) under assumption of a uniformly bounded mesh ratio,

0 < c ≤ h_{i−1}/h_{i} ≤ C < ∞, h_{i} := t_{i} − t_{i−1}.

Table 1. Approximation orders.

§2. Fourth–order interpolation methods

The rest of this short note consists of comments to some of the table entries. The proof of the stated convergence order m always follows the technique of deBoor, Höllig, and Sabin in [1]. Therefore only some hints concerning the definition of the methods and certain variations in the standard convergence proof are necessary.

2.1 Quadratic GC^{1} interpolation to H1 data

Just take the polynomial piece p_{i}(t) as the quadratic polynomial in BB form with control points f_{i−1}, Z_{i}, f_{i}, where Z_{i} is the intersection of tangents T_{i−1} and T_{i} at f_{i−1} and f_{i}.

2.2 Cubic GC^{1} interpolation to H1 data

Let p_{i}(t) be the cubic polynomial in BB form defined by control points f_{i−1}, Z_{i−1}^{+}, Z_{i}^{−}, f_{i}, where the points Z_{i}^{−} and Z_{i}^{+} lie on the “left” and “right” of f(t_{i}) on the tangent T_{i} at f(t_{i}) at a distance of ∥f_{i−1}−f_{i}∥/3 and ∥f_{i}−f_{i+1}∥/3 to f(t_{i}), respectively.

2.3 Cubic GC^{2} interpolation to H1 data

First use the method of 2.2 and evaluate the curvature (or the mean over the jump of the curvature) of the GC^{1} interpolant at the interpolation points. This gives O(h^{2}) estimates for κ_{i} that can be used to calculate a GC^{2} solution to the corresponding H2 problem, and the standard technique of [1] gives an error of O(h^{4}).

2.4 Quadratic GC^{1} interpolation to H0 data

The methods of [2] allow an expansion

\frac{γ(h_{1}, h_{2})}{h_{1} − h_{2}} = \frac{1}{2}θ_{1} + \frac{1}{3}θ_{2}(h_{1} + h_{2}) + O(h_{1}^{2}) + O(h_{2}^{2})  (5)

for the angle γ(h_{1}, h_{2}) between the chords f(t+h_{1})−f(t) and f(t+h_{2})−f(t), where θ_{1} = κ_{f}(t) and θ_{2} = κ′_{f}(t). Using four successive values of f near t and substituting chord length d_{n} := sgn h_{n}∥f(t + h_{n}) − f(t)∥ for the unknown arclength h_{n} between f(t + h_{n}) and f(t) yields two equations of type (5). Solving these will provide an O(h^{2}) estimate for θ_{1} = κ_{f}(t) and an O(h) estimate for θ_{2} = κ′_{f}(t), if the mesh ratio is uniformly bounded. Putting these into the expansion (see [2])

α(h) = \frac{1}{2}θ_{1}h + \frac{1}{3}θ_{2}h^{2} + O(h^{3})  (6)

for the angle α(h) between the tangent at f(t) and the chord f(t + h) − f(t) gives an O(h^{3}) approximation to α(h). The estimated H1 data values can be used to calculate a solution along the lines of 2.1. Substitution of arclength h by chordlength d is feasible as long as the asymptotic behavior d(h) = h + O(h^{3}) is sufficient for the required approximation order. Note that we regard curvature, arclength, chordlength, and angles as signed quantities.

2.5 Cubic GC^{1} interpolation to H0 data

Proceed as in 2.4 to get third order accurate data for the H1 problem, and then apply 2.2.

2.6 Cubic GC^{2} interpolation to H0 data

Use 2.5, 2.2, and 2.3 in a suitable way.

§3. A “bootstrapping” sixth–order method for H1 data

The methods of 2.2 and 2.3 gave fourth order accuracy by use of a second– order approximation of curvature values κ_{i}. To raise the overall error order to 6 in a parametrization–independent way, one has to provide fourth–order accurate estimates of κ_{i}. This can be done using an expansion

θ(h) = ∑_{i=1}^{4} θ_{i}h^{i} + O(h^{5})  (7)

as in [1], where θ(h) is the angle between tangents at f(t) and f(t + h). Furthermore, the curvature κ_{f}(t+h) is θ′(t+h). Now, for five consecutive H1 data points around t, four angles of the form θ(h_{i}) are given and one is tempted to solve a simple polynomial interpolation problem for data (h_{i}, θ(h_{i})) to get estimates of order O(h^{5−i}) for θ_{i}, i = 1, …, 4.

Unfortunately, the values h_{i} are unknown arclengths which can no more be substituted by chordlengths d_{i}, because the required accuracy is too high. Thus, we employ a “bootstrapping” technique to gradually raise the accuracy of estimates of h_{i}:

Step 1: Set h_{n}^{(1)} := d_{n}, θ_{3} = θ_{4} = 0 and use (7) to calculate approximations θ_{i}^{(1)} of order O(h^{3−i}) for i = 1, 2 with the three “nearest ” values of f to f(t).

Step 2: Put the chordlengths d = d_{n}, n = 1, 2, 3, 4 and the resulting approximations θ_{i}^{(1)}, i = 1, 2 into the expansion

h(d) = d + d^{3} \frac{θ_{1}^{2}}{24} + d^{4} \frac{θ_{1}θ_{2}}{12} + O(d^{5})  (8)

of the arclength h between f(t + h) and f(t) as a function of the chordlength d = ∥f(t+h)−f(t)∥. Such an expansion can easily be calculated by REDUCE, taking all nonlinearities into account. This gives new values h_{n}^{(2)} = h_{n}+O(h^{5}), and now the arclength values are accurate enough to apply polynomial interpolation of (h_{i}, θ(h_{i})) to get estimates of order O(h^{5−i}) for θ_{i}, i = 1, …, 4, if the mesh ratio is uniformly bounded.

The standard error analysis in [1] then yields an overall interpolation error of O(h^{6}) for f with κ_{f} ≠ 0, and of O(h^{4}) for f with κ_{f} ≥ 0.

References

1. deBoor, C., K. Höllig, and M. Sabin, High Accuracy Geometric Hermite Interpolation, Computer-Aided Geom. Design 4 (1987), 269–278

2. Schaback, R., Interpolation with piecewise quadratic visually C^{2} Bezier polynomials, to appear in Computer-Aided Geom. Design

3. Schaback, R., On Global GC^{2} Convexity Preserving Interpolation, in Mathematical Methods in Computer Aided Geometric Design, T. Lyche and L. L. Schumaker (eds.), Academic Press, New York, 1989

Special thanks go to Klaus Höllig for a number of valuable discussions in September 1988.