Polynomial meshes on some classes of planar compact domains ∗

Polynomial meshes on some classes of planar compact domains ^∗

F. Piazzon and M. Vianello

Department of Mathematics, University of Padova (Italy) March 18, 2013

Abstract

We construct low cardinality admissible meshes for polynomials on three classes of planar compact domains: cartesian graph domains, polar graph domains, and domains with piecewise C

boundary, that satisfy a Markov polynomial inequality.

2000 AMS subject classification: 41A10, 41A63, 65D10.

Keywords: Polynomial Inequalities, Norming Sets, Admissible Meshes, Planar Compact Domains, Graph Domains.

1 Planar cartesian and polar graph domains

Let K ⊂ R

be a polynomial determining compact domain (i.e., a polyno- mial vanishing there vanishes everywhere). We term family of (polynomial) norming sets for K any sequence of compact subsets N

⊆ K, n ∈ N, such that the following polynomial inequality holds

kpk

≤ C kpk

, ∀p ∈ P

, (1) where C > 0 is a constant and P

denotes the space of real d-variate poly- nomials of total degree at most n. Such a property is invariant under affine transformations of K. Here and below, kfk

denotes the sup-norm of a function bounded on the set X.

When the norming set N

is discrete and finite, and has cardinality O(n

) for some s ≥ d, the family is called an admissible mesh. An admissible mesh with s = d is called optimal; see [6, 9]. If in (1) we have a sequence C

instead

∗

Supported the ex-60% funds of the University of Padova, and by the INdAM GNCS.

1

Corresponding author, e-mail: [email protected]

of C, increasing at most polynomially with n, the mesh is called weakly admissible [6]. Admissible and weakly admissible meshes are important structures in multivariate polynomial approximation theory: for example, in [6] it is shown that they are nearly optimal for least squares approximation, and contain Fekete-like interpolation sets with a slowly increasing Lebesgue constant. Computational techniques to extract approximate Fekete and Leja points from polynomial meshes have been recently developed in [1, 2, 3, 15, 16], where the mesh cardinality control is an essential feature for the effectiveness of the methods. Among the possible applications, we recall that approximate Fekete points have been recently used in the numerical PDEs context, see, e.g., [10, 18].

In the recent literature, some attention has been devoted to the con- struction of admissible meshes for multidimensional compact sets. In [6, Thm.5], it has been shown that any compact set which satisfies a Markov polynomial inequality with exponent r has an admissible mesh with O(n

) cardinality. We recall that a Markov polynomial inequality is a polynomial inequality of the form

k∇pk

≤ Mn

kpk

, ∀n ∈ N, p ∈ P

, (2) where k∇pk

= max

k∂p/∂x

k

, i = 1, . . . , d. A compact set that admits an inequality like (2) is often termed a Markov compact.

On the other hand, the existence of optimal (or near-optimal) admissible meshes has been proved constructively for several families of bidimensional and multidimensional compacts, such as for example polygons and polyhe- dra, euclidean balls, subanalytic sets, convex bodies and starlike domains with smooth boundary; cf., [5, 9, 11, 14].

In this note we focus on three general classes of compact domains in the bidimensional case (d = 2), namely cartesian graph domains, polar graph domains (e.g., starlike domains), and domains with piecewise C

boundary, satysfying a Markov polynomial inequality with exponent r = 2. We prove that they have admissible meshes with O(n

) cardinality, which is interme- diate between optimality (s = 2) and the standard general construction by Calvi and Levenberg (s = 4).

We begin by proving the following:

Proposition 1 Let K be a planar compact cartesian graph domain

K = {(x, y) : a ≤ x ≤ b , g

(x) ≤ y ≤ g

(x) } (3) where g

≤ g

are any two continuous functions defined in [a, b], or a planar compact polar graph domain

K = {(x, y) = (x

+ ρ cos θ, y

+ ρ sin θ) : α ≤ θ ≤ β , r

(θ) ≤ ρ ≤ r

(θ) }

(4)

where (x

, y

) is any point, and 0 ≤ r

≤ r

are any two continuous functions defined in [α, β]. Moreover, assume that K satisfies a Markov polynomial inequality with constant M and exponent 2.

Then, K has a norming set given by the union of O(n) curves and an admissible mesh with O(n

) cardinality which lies on the norming curves.

Proof. By the arguments of [6, Thm.5], it is not difficult to show that K has an admissible mesh with O(n

) points, which is a subset of a O(n

) × O(n

) grid. Indeed, to be an admissible mesh with constant C = 1/(1 − λ), it is sufficient that for any point P ∈ K there exists a point A of the mesh such that

|P − A| ≤ δ

= 2c

M n

, (5)

where 0 < c < c

, λ = 4ce

< 1, c

= 0.175... being the solution of the equation 4te

= 1.

We begin by considering a grid of equally spaced points, with suitable O(1/n

) spacings in the projections of K on the cartesian axes. Take in both directions a spacing smaller than δ

/ √

2, so that (5) is satisfied by the grid points. The compact K is now contained in the union of O(n

) vertical strip segments.

On each strip, consider the “highest” and the “lowest” rectangle of the grid which instersects K, fix a point of K in both, say (u, v) and (z, w), and add to the mesh these two points together with the intersection points of the vertical lines x = u and x = z with the horizontal lines of the grid between y = w = g

(z) and y = v = g

(u) (observe that all such intersection points belong necessarily to the graph domain K). The points obtained by this construction clearly belong to a new (non equispaced) O(n

) × O(n

) grid, say {(x

, y

) }, and form an admissible mesh for K, with constant C = 1/(1 − λ), since by construction they still satisfy property (5).

It is clear that the union of the segments {x = x

, g

(x

) ≤ y ≤ g

(x

) } is a norming set for K, with the same constant C. Now, take for example the Chebyshev points of degree mn on each segment, namely the points

{(x

, y

) = (x

, g

(x

)(1 + τ

)/2 + g

(x

)(1 − τ

)/2) }

where the {τ

}, 1 ≤ k ≤ mn, are the zeros of T

(t), m > 1, in ( −1, 1).

Since these points form an admissible mesh for the segment, with constant 1/ cos(π/2m), cf. [5], the union of the points of all the segments is then an admissible mesh for K, say A

, such that

kpk

≤ 1

(1 − λ) cos(π/2m) kpk

, ∀p ∈ P

, (6)

with card( A

) = O(n

) × mn = O(n

). Observe now that this mesh lies on

the union of the mn curves

Γ

= {(x, f

(x)) , x ∈ [a, b]} , f

(x) = g

(x)(1 + τ

)/2 + g

(x)(1 − τ

)/2 , (7) 1 ≤ k ≤ mn, which thus form a norming set for K.

In the polar case, the proof is quite similar. We begin by considering, instead of a rectangle, the smallest disk containing K. Then, we take a suitably fine polar grid, where we have essentially to manage the diameter of the grid curvilinear rectangles at the boundary of the disk, and proceed exactly as above, where the role of the vertical lines is played by rays and that of the horizontal lines by concentric circles.

Eventually, we get an admissible mesh of O(n

) points, which belong to a new polar grid with O(n

) ray segments between r

(θ) and r

(θ). These ray segments form a norming set for K. Taking the Chebyshev points of degree mn on each segment, we construct an admissible mesh with O(n

) cardinality, whose points lie on the set of norming curves ρ = r

(θ) = r

(θ)(1 + τ

)/2 + r

(θ)(1 − τ

)/2. 

Remark 1 Observe that a compact cartesian graph domain like (3) sat- isfies a Markov inequality with exponent 2 if it is convex with nonempty interior [17], i.e., g

is a convex and g

a concave function. Another suf- ficient condition is that the functions g

and g

are Lipschitz continuous, and g

(a) 6= g

(a), g

(b) 6= g

(b), since in this case the boundary of K is locally the graph of a Lipschitz-continuous function, i.e., K is a Lipschitz domain, and thus satisfies a uniform interior cone condition [8]. The same holds true when g

(a) = g

(a) but g

(a) 6= 0 or g

(a) 6= 0, or g

(b) = g

(b) but g

(b) 6= 0 or g

(b) 6= 0.

It is worth noticing, however, that the existence of a Markov polynomial inequality is not necessary for a graph domain to possess an admissible mesh. This has been shown by Example 3 in [9], where an admissible mesh with cardinality O(n

) has been constructed in a cartesian graph domain with an exponential cusp, that does not satisfy a Markov inequality for any exponent.

When the conditions above are satisfied, our result improves that of [9], in the case of planar graph domains with g

, g

6∈ C

. Indeed, in [9]

it is proved that any planar graph domain with g

, g

∈ C

possesses an admissible mesh with O(n

) points.

In the polar case, sufficient conditions are the fact that the boundary curve ρ = r(θ) is convex, or that the function r(θ) is C

and the boundary curve is regular (the tangent vector does not vanish and there are no cusps), so that the domain is a Lipschitz domain [8].

Remark 2 The existence of a Markov polynomial inequality is not neces-

sary for a graph domain, to possess a norming set given by the union of O(n)

curves, and this can be proved with a reasoning similar to that developed above. Indeed, consider a cartesian graph domain like (3), and any of the segments I(z) = {(z, y) : g

(z) ≤ y ≤ g

(z) } for a fixed value of z ∈ [a, b].

The points A

(z) = {(z, g

(z)(1 + τ

)/2 + g

(z)(1 − τ

)/2), 1 ≤ k ≤ mn}

form an admissible mesh for the segment, thus S

z∈[a,b]

A

(z) is a norming set for K with constant C = 1/ cos(π/2m), which concides with the union of the mn curves (7).

The same observation applies in the polar case, considering the ray seg- ments I(φ) = {(ρ, φ) : r

(φ) ≤ ρ ≤ r

(φ) } for a fixed value of φ ∈ [0, 2π], and the points A

(φ) = {(r

(φ)(1 + τ

)/2 + r

(φ)(1 − τ

)/2, φ), 1 ≤ k ≤ mn}.

2 Planar domains with piecewise C ² boundary

In this section we show that admissible meshes with O(n

) cardinality can be constructed, via polygonal approximation of the boundary, on any pla- nar compact simply-connected domain whose boundary is a piecewise C

generalized regular parametric curve. A preliminary version of this result in the smooth case has been discussed in the unpublished thesis [13].

The proof is based on the perturbation result recently proved in [12], which uses the notion of Hausdorff distance of two d-dimensional compact sets, namely

δ(K, H) = inf {η > 0 : K ⊆ H + B

[0, η] and H ⊆ K + B

[0, η] } where B

[0, η] denotes the closed ball (in the max-norm) centered at 0 with radius η.

For the reader’s convenience, we recall such a result in the real case.

Theorem 1 (see [12]) Let K ⊂ R

satisfy a Markov polynomial inequality with constant M and exponent r, cf. (2). Assume that there exists a compact K

, n ∈ N, such that the polynomial inequality

kpk

≤ C

kpk

, ∀p ∈ P

(8) is satisfied for a suitable finite subset N

⊂ K

, and δ(K, K

) ≤ e

in the Hausdorff distance δ, with

e

= e

(θ) = θ

(1 + C

)M n

(9)

for a fixed θ ∈ (0, θ

/d), where θ

= 0.703 . . . solves the equation

t exp (t/2) = 1 . (10)

Consider a small perturbation of N

, say e N

⊂ K, constructed by choosing

a point ˜ ξ ∈ B

[ξ, e

] ∩ K for every ξ ∈ N

.

Then, the following polynomial inequality holds

kpk

≤ C

1 − dθ exp (dθ/2) kpk

, ∀p ∈ P

. (11) This result has several applications. For example, it shows that (weakly) admissible meshes are “stable” under small perturbations on Markov com- pacts (in this case one takes K

≡ K). On the other hand, it provides a tool for constructing a (weakly) admissible mesh on a Markov compact by suitable “simpler” approximating compacts. This is just the approach pursued in the following:

Proposition 2 Let K be a planar simply-connected compact domain (the closure of a bounded simply-connected open set in R

), with boundary

∂K = γ([a, b]) , (12)

where γ(t) = (x(y), y(t)), t ∈ [a, b], is a closed (continuous) piecewise C

parametric curve, simple and generalized regular, i.e., it has no multiple points, no singular points (points where the tangent vectors vanish) and no cusps (points where the left and right tangent vectors have opposite direc- tions).

Then, K has an admissible mesh with O(n

) cardinality.

Proof. For the relevant geometric notions concerning the boundary curve (generalized regularity, ...), we refer the reader to [4] and references therein.

We observe that K satisfies a Markov polynomial inequality with exponent 2, since it is a Lipschitz domain, the boundary curve being simple and regular (cf. [8]).

Now, consider a piecewise linear interpolation with stepsize h of γ, made on each subinterval of the parameter interval determined by a pair of con- secutive breakpoints (the finite number of points where C

regularity does not hold but left and right first and second derivatives exist). Let us term γ

(t), t ∈ [a, b], the corresponding polygonal path. The global uniform error of such an approximation, is

kγ − γ

k

= ε(h) = O(h

) .

We recall that by triangulation and finite union, any polygon has an admis-

sible mesh with the same constant of a triangle, namely C = 1/ cos

(π/2m),

and cardinality mn

times the number of triangles; cf. [5, 7]. For example,

for m = 2 the constant is C = 2. Hence we have ε(h) ≤ e

, where e

is defined in (9) with C

≡ C = 1/ cos

(π/2m) and r = 2, by a stepsize

h = O(1/n). This means that the interpolating polygonal path γ

is formed

by O(n) linear segments.

Consider the polygon K

whose boundary is given by the polygonal path γ

. Using the fact that kγ

− γ

k

= O(h) (the derivative of γ

being piecewise constant), by a slight modification of the arguments in [4], one can prove that the polygonal path remains simple, provided that h ≤ h

(for a suitable h

which is independent of n). Then the polygon K

is a simple polygon with µ = O(n) sides, and can be splitted into ν = µ − 2 triangles {T

}, K = S

j

T

. Since, as already recalled above, any triangle has an admissible mesh with mn

points, say A

, we eventually get an admissible mesh for the polygon K

, say N

= S

j

A

, with card( N

) = νmn

= O(n

) and constant C = 1/ cos

(π/2m), m > 1.

By construction, the symmetric set difference K △K

is covered by the union of the segments sγ(t) + (1 − s)γ

(t), s ∈ [0, 1], t ∈ [a, b], whose length is not greater than e

, i.e., any point of K △K

is at a distance not greater than e

from a point of ∂K, which implies that δ(K, K

) ≤ e

. Applying Theorem 1 we can then construct, by a small perturbation of the possible points of N

that are not in K, an admissible mesh ˜ N

for K such that

kpk

≤ 1

(1 − 2θ exp(θ)) cos

(π/2m) kpk

, ∀p ∈ P

, (13) where card( ˜ N

) ≤ card(N

) = O(n

). 

Remark 3 In the recent literature, the notion of weakly admissible mesh play also a relevant role. The definition is like that of an admissible mesh, but instead of a constant C in (1) a sequence of constants C

is allowed, provided that these increase at most polynomially with n.

In many cases weakly admissible meshes are known with cardinality O(n

) and sequence of constants increasing logarithmically. For example, since the Chebyshev-Lobatto points of degree are a weakly admissible mesh for the interval with C

= O(log n), we could restate Proposition 1 in terms of existence of a weakly admissible mesh for a graph domain, with constants C

= O(log n).

On the other hand, in the case of Proposition 2 resorting to weakly admissible meshes is not convenient. In fact, it is known (again by poly- gon triangulation) that any polygon has a weakly admissible mesh with C

= O(log

n) (cf. [7]), but then these would enter the definition (9) of e

, leading to a stepsize for the piecewise linear approximation of the bound- ary h = O(1/(n log n)), and eventually to a cardinality O(n

log n) for the polynomial mesh.

Remark 4 The assumptions on the boundary curve ensure that the domain

is a Lipschitz domain (which satisfies a uniform interior cone condition and

thus a Markov polynomial inequality with exponent 2) and that the approx-

imating polygonal path is simple. However, these conditions can hold also

in the presence of a nonregular boundary.

Consider for example the cardioid whose boundary is given by the para- metric curve (x(t), y(t)) = ((1 − cos(t)) cos(t), (1 − cos(t)) sin(t)), t ∈ [0, 2π].

This domain clearly satisfies an interior cone condition. Moreover, any piece- wise linear interpolating path is simple, so that following the construction in the proof of Proposition 2, by the same perturbation argument we obtain an admissible mesh with O(n

) cardinality, even though the boundary curve is singular at the origin.

References

[1] L. Bos, J.-P. Calvi, N. Levenberg, A. Sommariva and M. Vianello, Ge- ometric Weakly Admissible Meshes, Discrete Least Squares Approxi- mation and Approximate Fekete Points, Math. Comp. 80 (2011), 1601–

1621.

[2] L. Bos, S. De Marchi, A. Sommariva and M. Vianello, Computing mul- tivariate Fekete and Leja points by numerical linear algebra, SIAM J.

Numer. Anal. 48 (2010), 1984–1999.

[3] L. Bos, S. De Marchi, A. Sommariva and M. Vianello, Weakly Admissi- ble Meshes and Discrete Extremal Sets, Numer. Math. Theory Methods Appl. 4 (2011), 1–12.

[4] L. Bos and M. Vianello, On simple approximations to simple curves, Dolomites Res. Notes on Approx. DRNA 3 (2010), 1–6.

[5] L. Bos and M. Vianello, Low cardinality admissible meshes on quad- rangles, triangles and disks, Math. Inequal. Appl. 15 (2012), 229–235.

[6] J.P. Calvi and N. Levenberg, Uniform approximation by discrete least squares polynomials, J. Approx. Theory 152 (2008), 82–100.

[7] M. Gentile, A. Sommariva and M. Vianello, Polynomial interpolation and cubature over polygons, J. Comput. Appl. Math. 235 (2011), 5232–

5239.

[8] M.C. Delfour and J.-P. Zol´esio, Shapes and Geometries, SIAM, Philadelphia, 2011.

[9] A. Kro´ o, On optimal polynomial meshes, J. Approx. Theory 163 (2011), 1107–1124.

[10] R. Pasquetti and F. Rapetti, Spectral element methods on unstructured

meshes: which interpolation points?, Numer. Algorithms 55 (2010),

349–366.

[11] F. Piazzon and M. Vianello, Analytic transformations of admissible meshes, East J. Approx. 16 (2010), 389–398.

[12] F. Piazzon and M. Vianello, Small perturbations of polynomial meshes, Appl. Anal., published online 18 January 2012.

[13] V. Piciocchi, Construction of polynomial admissible meshes on smooth planar compacts, Laurea thesis in Mathematics (in Italian), University of Padova, 2012 (advisor: M. Vianello).

[14] W. Pl´esniak, Nearly optimal meshes in subanalytic sets, Numer. Algo- rithms 60 (2012), 545-553.

[15] A. Sommariva and M. Vianello, Computing approximate Fekete points by QR factorizations of Vandermonde matrices, Comput. Math. Appl.

57 (2009), 1324–1336.

[16] A. Sommariva and M. Vianello, Approximate Fekete points for weighted polynomial interpolation, Electron. Trans. Numer. Anal. 37 (2010), 1–

22.

[17] D. R. Wilhelmsen, A Markov inequality in several dimensions, J. Ap- prox. Theory 11 (1974), 216–220.

[18] P. Zitnan, The collocation solution of Poisson problems based on ap-

proximate Fekete points, Eng. Anal. Bound. Elem. 35 (2011), 594–599.