9512.net

# Asymptotic Approximation of Convex Curves the Hausdorff Metric Case

Asymptotic Approximation of Convex Curves; the Hausdor? Metric Case
Monika Ludwig

1

Introduction

Let C and D be closed convex curves in the Euclidean plane. Their Hausdor? distance δ H (C, D) is de?ned by δ H (C, D) = max{sup inf
p∈C q∈D

p ? q , sup inf
q∈D p∈C

p ? q },

i where . is the Euclidean norm. Let Pn (C) be the set of closed convex polygons which are inscribed into C and have at most n vertices. Beginning with the work of L. Fejes T?th (cf. the surveys [3], [4]), there are investigations on the o asymptotic behavior as n → ∞ of the distance of C to its best approximating inscribed polygons with at most n vertices, i.e., of i i δ H (C, Pn ) = inf{δ H (C, Pn ) : Pn ∈ Pn (C)}, c and the similarly de?ned distance δ H (C, Pn ) for circumscribed polygons. In the following we assume that C is of class C 2 and has positive curvature. i c In this case the asymptotic behavior as n → ∞ of δ H (C, Pn ) and δ H (C, Pn ) was described by L. Fejes T?th [1],[2]: o

δ

H

i (C, Pn )

H

c (C, Pn )

1 ? 8

l 0

2

κ

1/2

(t)dt

1 , n2

(1)

where κ(t) is the curvature of C given as a function of the arclength t and l the length of C. See also McClure and Vitale [7] and for asymptotic formulae for approximation with respect to the Hausdor? metric in higher dimensions R. Schneider [8],[9] and P.M. Gruber [5]. In this article we extend the asymptotic formulae (1) by deriving the second i c terms in the asymptotic expansions of δ H (C, Pn ) and δ H (C, Pn ). This complements results derived for approximation with respect to the symmetric di?erence metric in [6].

1

2

Some De?nitions

Let Pn be a polygon inscribed in C and let p1 , . . . , pn be its successive vertices. Denote by hi the maximal distance that a point lying on C between pi?1 and pi can have from the line segment connecting pi?1 and pi . Thus, δ H (C, Pn ) = maxi=1,...,n hi . For a convex curve C with positive curvature and n large enough it is easy to see that h1 = h2 = . . . = hn (2) for all best approximating polygons. A similar statement holds for circumscribed polygons. Because of the asymptotic formulae (1), we introduce a new parameter for C by
t

s(t) =
0

κ1/2 (τ )dτ, 0 ≤ t ≤ l,

(3)

where t is the arclength of C. De?ne
l

λ=
0

κ1/2 (τ )dτ.

In the following C is always of class C 4 with positive curvature and given in a parametrization x(s), 0 ≤ s ≤ λ, where s is de?ned by (3). By we denote di?erentiation with respect to s.

3

i Asymptotic Expansion for δ H (C, Pn)

Lemma 1 For 0 ≤ r ≤ s ≤ λ, let h(r, s) be the maximal distance that a point lying on C between x(r) and x(s) can have from the line segment connecting these points. Then 1 1 5 h(r, s) = (s?r)2 ? κ(r) + κ?1 (r)κ (r) ? κ?2 (r)(κ (r))2 (s?r)4 +o((s?r)4 ), 8 384 6 uniformly for all 0 ≤ r ≤ s ≤ λ as (s ? r) → 0. Proof. The distance of a point x(σ), r ≤ σ ≤ s, to the line segment joining x(r) and x(s) is given by x(s) ? x(r) |x(σ) ? x(r), |, x(s) ? x(r) where | . , . | is the determinant. The maximal distance h(r, s) is attained for a point x(σ) for which x(s) ? x(r) | = 0. |x (σ), x(s) ? x(r)

2

By this equation a function σ = φ(r, s) is de?ned with the help of which h(r, s) can be written as h(r, s) = |x(φ(r, s)) ? x(r), x(s) ? x(r) |. x(s) ? x(r)

Simple but rather lengthy calculations give the Taylor polynomial of order four of h(r, s) and the statement of the lemma. 2 We de?ne 5 i kH (s) = κ(s) + κ?1 (s)κ (s) ? κ?2 (s)(κ (s))2 6 and are able to formulate the ?rst theorem. Theorem 1 Let C ∈ C 4 be a convex curve with positive curvature. Then δ as n → ∞. Proof: We consider a sequence of best approximating polygons with vertices at x(sni ), i = 1, . . . , n. As a ?rst step we derive a simple asymptotic formula for the λni = sni ? sn,i?1 . By (2) we have
i hn1 = hn2 = . . . = hnn = δ H (C, Pn ). H i (C, Pn )

1 λ2 λ3 ? ? 8 n2 384

λ i kH (s)ds 0

1 1 + o( 4 ) 4 n n

Since λni → 0 as n → ∞, we see from (1) and the terms of second order in Lemma 1, that for any ε > 0, there is a positive integer n0 such that λ2 λ2 (1 ? ε) ≤ hni ≤ 2 (1 + ε) 8n2 8n 1 2 1 λni (1 ? ε) ≤ hni ≤ λ2 (1 + ε) 8 8 ni for all n ≥ n0 . Combining these inequalities gives 1 ? ε λ2 1 + ε λ2 2 ≤ λni ≤ . 1 + ε n2 1 ? ε n2 λ 1 + o( ) n n uniformly as n → ∞, which is the desired simple asymptotic formula. λni = 3 From this we see that (4) and

For any i, j, 0 < i, j < n, we have hni = hnj . Therefore, Lemma 1 and (4) give 1 2 1 i 1 1 1 i 1 λni ? kH (sn,i?1 )λ4 + o( 4 ) = λ2 ? kH (sn,j?1 )λ4 + o( 4 ). ni nj nj 8 384 n 8 384 n Extracting the square root of these equations gives 1 i 1 1 i 1 λni ? kH (sn,i?1 )λ3 + o( 3 ) = λnj ? kH (sn,j?1 )λ3 + o( 3 ). (5) ni nj 96 n 96 n We de?ne λ λni = + εni n 1 and have by (4) εni = o( n ). Combining this with (5) we obtain 1 i λ3 1 i λ3 1 kH (sn,i?1 ) 3 + εnj ? kH (sn,j?1 ) 3 + o( 3 ). 96 n 96 n n n In these equations we sum on j from 1 to n, and since j=0 εnj = 0, ?nd that εni = nεni = Therefore,
n→∞

1 i λ3 1 λ2 kH (sn,i?1 ) 2 ? 96 n 96 n2

n i kH (sn,j?1 )λnj + o( j=0 λ

1 ). n2

lim n

3

1 i λ3 εni ? kH (sn,i?1 ) 3 96 n
λ

λ2 =? 96

i kH (s)ds 0

and λ 1 i λ3 λ2 λni = + kH (sn,i?1 ) 3 ? n 96 n 96

i kH (s)ds 0

1 1 + o( 3 ) 3 n n

(6)

uniformly as n → ∞. i Using (6), we obtain the asymptotic expansion of δ H (C, Pn ). Lemma 1 and (6) give
i δ H (C, Pn ) =

1 n 1 n λ2 1 i 1 ni hni = ? kH (sn,i?1 )λ4 + o( 4 ) = ni n i=1 n i=1 8 384 n
λ i kH (s)ds 0

1 n 1 λ2 1 i λ 4 λ3 + kH (sn,i?1 ) 4 ? = n i=1 8 n2 48 n 48 1 i λ4 1 ? kH (sn,i?1 ) 4 + o( 4 ) . 384 n n Therefore, δ and
n→∞ H i (C, Pn )

1 ? n4

λ2 λ3 ? 2 =? 8n 384 λ2 ? 2 8n

λ i kH (s)ds 0

1 1 + o( 4 ) n4 n

lim n

4

δ

H

i (C, Pn )

λ3 =? 384

λ i kH (s)ds. 2 0

4

Comparing this result with the asymptotic expansion for approximation with respect to the symmetric di?erence metric
i δ S (C, Pn ) ?

1 λ 3 1 λ4 ? 12 n2 2 5!

λ

k(s)ds
0

1 1 + o( 4 ) 4 n n

(cf. [6]), where λ is the a?ne length of C, s the a?ne arclength and k(s) the i a?ne curvature of C, we see that kH plays the same role in the case of the Hausdor? metric as the a?ne curvature in the case of the symmetric di?erence metric. But whereas in the case of the symmetric di?erence metric the second term in the asymptotic expansion for approximation by circumscribed polygons again depends on k(s), for the Hausdor? metric it depends on a function di?erent i from kH (see the following section).

4

c Asymptotic Expansion for δ H (C, Pn)

Lemma 2 For 0 ≤ r ≤ s ≤ λ, let k(r, s) be the maximal distance that a point lying on C between x(r) and x(s) can have from the point where the tangents at x(r) and x(s) meet. Then 1 5 1 7 k(r, s) = (s ? r)2 + κ(r) + κ?1 (r)κ (r) ? κ?2 (r)(κ (r))2 (s ? r)4 8 384 5 30 + o((s ? r)4 ), uniformly for all 0 ≤ r ≤ s ≤ λ as (s ? r) → 0. Proof. The point where the tangents at x(r) and x(s) meet is given by y(r, s) = x(r) + |x(s) ? x(r), x (s)| x (r). |x (r), x (s)|

For a point x(σ) with maximal distance from that point we have x (σ) · (x(σ) ? y(r, s)) = 0. By this equation a function σ = φ(r, s) is de?ned, with the help of which we get k(r, s) = x(φ(r, s)) ? y(r, s) . As in the proof of Lemma 1 rather lengthy calculations give the Taylor polynomial of order four of k(r, s) and the statement of the lemma. 2 We de?ne 1 7 c kH (s) = κ(s) + κ?1 (s)κ (s) ? κ?2 (s)(κ (s))2 5 30 and get the following theorem. 5

Theorem 2 Let C ∈ C 4 be a convex curve with positive curvature. Then δ as n → ∞. The proof of this theorem is analogous to that of Theorem 1.
H c (C, Pn )

1 λ2 5λ3 ? + 8 n2 384

λ c kH (s)ds 0

1 1 + o( 4 ) 4 n n

Acknowledgements
I am obliged to Professor Gruber for many valuable suggestions.

References
[1] Fejes T?th L., Approximation by polygons and polyhedra, Bull. Amer. Math. o Soc., 54 (1948), 431-438. [2] Fejes T?th L., Lagerungen in der Ebene, auf der Kugel und im Raum, o Springer, Berlin 1953, 1972. [3] Gruber P.M., Approximation of convex bodies, In: Convexity and its applications (ed. by P.M. Gruber and J.M. Wills), Birkh¨user, Basel 1983. a [4] Gruber P.M., Aspects of approximation of convex bodies, In: Handbook of convex geometry (ed. by P.M. Gruber and J.M. Wills), North-Holland, Amsterdam 1993. [5] Gruber P.M., Asymptotic estimates for best and stepwise approximation of convex bodies I, Forum Math., 5 (1993), 281-297. [6] Ludwig M., Asymptotic approximation of convex curves, Arch. Math., 63 (1994), 377-384 [7] McClure D.E., Vitale R.A., Polygonal approximation of plane convex bodies, J. Math. Anal. Appl., 51 (1975), 326-358. [8] Schneider R., Zur optimalen Approximation konvexer Hyper?¨chen durch a Polyeder, Math. Ann., 256 (1981), 289-301. [9] Schneider R., Polyhedral approximation of smooth convex bodies, J. Math. Anal. Appl., 128 (1987), 470-474.

6