9512.net
甜梦文库
当前位置:首页 >> >>

Approximation of convex bodies and a momentum lemma for power diagrams


Approximation of convex bodies and a momentum lemma for power diagrams
K? aroly B¨ or¨ oczky, Jr. and Monika Ludwig
¨ The research was partially supported by Osterreichisches Ost-West Programm. The ?rst named author was also supported by OTKA.

Abstract The volume of the symmetric di?erence of a smooth convex body in I E 3 and its bestapproximating polytope with n vertices is asymptot1 ically a constant multiple of n . We determine this constant and the similarly de?ned constant for approximation with a given number of facets by solving two isoperimetric problems for planar tilings.
1991 AMS subject classi?cation: 52C20, 52A27 Keywords: asymptotic approximation, power diagram, Laguerre tiling, momentum lemma

1

Introduction and statement of results

Let C be a convex body in Euclidean d-space I E d , i.e., a compact convex i set with non-empty interior, and denote by Pn and P(cn) the set of polytopes with at most n vertices inscribed to C and the set of polytopes with at most n facets circumscribed to C , respectively. Denote by δ (., .) the symmetric di?erence metric. Beginning with the work of L. Fejes T? oth [2], there are many investigations (cf. the survey [5]) on the asymptotic behavior as n → ∞ of the distance of C to its best approximating polytopes with at most n vertices or facets, i.e., of
i i δ (C, Pn ) = inf {δ (C, P ) : P ∈ Pn }

1

and δ (C, P(cn) ) = inf {δ (C, P ) : P ∈ P(cn) }. For C ? I E 3 with boundary of di?erentiability class C 2 and positive Gaussian curvature κC , L. Fejes T? oth [2], p. 152, indicated that 1 i )? √ δ (C, Pn 4 3 and δ (C, P(cn) ) ? 5 √ 36 3 κC (x) 4 dσ (x)
1

2

bd C

1 n
2

(1)

bd C

κC (x) 4 dσ (x)

1

1 n

(2)

as n → ∞, where σ is the surface area measure in I E d . These formulae were proved by P.M. Gruber in [3] and [4], for the planar case see [8] and for d > 3 [6]. We are interested in the analogues of (1) and (2) for the problem of approximation by general polytopes, i.e., polytopes that are not necessarily inscribed or circumscribed to C . Let Pn and P(n) denote the sets of polytopes with at most n vertices and n facets, respectively, and de?ne δ (C, Pn ) and δ (C, P(n) ) as above. It is shown in [7] that there are positive constants ldeld?1 and ldivd?1 (depending only on d) such that for a convex body C ? I E d of class C 2 and with positive Gaussian curvature, 1 δ (C, Pn ) ? ldeld?1 2 and 1 δ (C, P(n) ) ? ldivd?1 2
bd C

bd C

κC (x)

1 d+1

dσ (x)

d+1 d?1

1 n d?1
2

(3)

(4) 2 n d?1 as n → ∞. These constants are de?ned by means of Laguerre tilings, which are also known as power diagrams (cf. [1]). The values of these constants are known only for d = 2 (ldel1 = ldiv1 = 1/16, cf. [7]), for d > 3 it seems to be di?cult to determine the exact value of these constants, cf. [6]. We will determine the values of ldel2 and ldiv2 . These constants are de?ned in [7] in the following way. Let L = {(a1 , r1 ), . . . , (am , rm )} with a1 , . . . , a m ∈ I E 2 and r1 , . . . , rm ≥ 0, and de?ne the sets V1 , . . . , Vm by
2 2 Vi = {x ∈ [0, 1]2 : (x ? ai )2 ? ri ≤ (x ? aj )2 ? rj , j = 1, . . . , m}.

κC (x)

1 d+1

dσ (x)

d+1 d ?1

1

2

Then L is called a Laguerre tiling of [0, 1]2 with the tiles V1 , . . . , Vm . Set
m

v (L) =
i=1 V
i

2 |(x ? ai )2 ? ri |dx

and de?ne ldiv2 = lim n inf {v (L) : L has at most n tiles},
n→∞

cf. [7]. Denote by Pk the regular k -gon centered at the origin o and of area |Pk | = 1. For a convex domain C , set I (C, r) =
C

|x2 ? r2 |dx

and choose ρk such that I (Pk , ρk ) ≤ I (P, r) for all r ≥ 0. THEOREM 1 Let {Q1 , . . . , Qn } be a tiling of [0, 1]2 with convex tiles, ai ∈ I E 2 and ri ≥ 0, i = 1, . . . , n. Then
n i=1 Qi 2 |(x ? ai )2 ? ri | dx ≥

I (P6 , ρ6 ) . n

This theorem provides a lower bound for ldiv2 and taking tilings with regular hexagons then shows that this bound is asymptotically optimal. Thus, calculating I (P6 , ρ6 ) gives Corollary 1 ldiv2 = 5 1 √ ? . 18 3 4π

In the de?nition of ldel2 , we have to count the number of vertices in the tiling of [0, 1]2 and set ldel2 = nlim n inf {v (L) : L has at most n vertices}, →∞ cf. [7].

3

THEOREM 2 Let {Q1 , . . . , Qm } be a tiling of [0, 1]2 with convex tiles, ai ∈ I E 2 and ri ≥ 0, i = 1, . . . , m, with no more than n vertices. Then
m i=1 Qi 2 |(x ? ai )2 ? ri | dx ≥

I (P3 , ρ3 ) . 2(n ? 2)

This provides a lower bound for ldel2 and considering tilings with regular triangles then gives Corollary 2 1 1 . ldel2 = √ ? 6 3 8π That this is the correct value, was conjectured in [3]. The classical momentum lemma of L. Fejes T? oth (cf. [2], p. 198) states that for a non–negative monotonous function g , the extremum of the integral g (|x|) dx
P

over k –gons P with given area is attained for the regular k –gon. A simple consequence is that I (P, 0) ≥ I (Pk , 0)|P |2 , which can be used to prove (2), cf. [4]. In the proof of Theorems 1 and 2, we need the following analogue of the momentum lemma: THEOREM 3 If P is a convex k -gon, k ≥ 3, then I (P, r) ≥ I (Pk , ρk )|P |2 . Note that similar arguments with simpler calculations than for general approximation would yield (1).

2

Some general observations

Let B (ρ) be the circle centered at the origin and with radius ρ. Letting r vary and calculating the critical point of I (C, r) shows LEMMA 1 Let C be a convex domain and let ρ be chosen such that I (C, ρ) ≤ I (C, r) for all r ≥ 0. Then |C ∩ B (ρ)| = |C \B (ρ)|.

4

Using this, we see that B (ρk ) ? Pk for k = 3, . . .. Thus, elementary calculations give I (Pk , ρk ) = tan π 1 1 k + ? . π 2k tan k 6k 4π (5)

LEMMA 2 Let C be a convex domain and r ≥ 0. If o ∈ int C , then I (C, r) ≥ 1.1 · I (P3 , ρ3 ) · |C |2 . Proof: Since C is convex and o ∈ int C , we can choose a (closed) half-plane H containing o on its boundary such that C ? H . Choose r0 and r1 satisfying |B (r1 )\B (r)| = |B (r)\B (r0 )| = |C | and de?ne G(r, |C |) = (B (r1 )\ int B (r0 )) ∩ H . If x ∈ C \B (r) is not in B (r1 )\B (r), then x2 ? r2 ≥ max{u2 ? r2 : u ∈ B (r1 )\B (r)} and if x ∈ C ∩ B (r) is not in B (r)\B (r0 ), then r2 ? x2 ≥ max{r2 ? u2 : u ∈ B (r)\B (r0 )}. Thus (x2 ? r2 ) dx ≥
C \ B (r ) G(r,|C |)\B (r)

(x2 ? r2 ) dx (r2 ? x2 ) dx.
G(r,|C |)∩B (r )

and (r2 ? x2 ) dx ≥
C ∩ B (r )

Therefore I (C, r) ≥ I (G(r, |C |)). Combining this with I (G(r, |C |)) = 1 1 |C |2 ≥ 1.1 · √ ? |C |2 = 1.1 · I (P3 , ρ3 )|C |2 2π 3 3 4π 2

where (5) was used, proves the lemma.

5

3

An auxiliary function

Let T = T (t) be a triangle with a right angle, |T | = 1 and an angle t at o. There always exists an optimal ρ = ρ(t), such that I (T (t), ρ(t)) ≤ I (T (t), r) for all r ≥ 0. De?ne c(t) = I (T (t), ρ(t)) for 0 < t < π/2. With the help of c(t) we can give a sharp lower bound for I (T, r) for general triangles T . LEMMA 3 Let T be a triangle with an angle 2 t at o. Then 1 I (T, r) ≥ c(t)|T |2 . 2 Proof: First, we show that among all such triangles T and r ≥ 0, there is a triangle S and a ρ ≥ 0 such that I (T, r) I (S, ρ) ≥ , 2 |T | |S |2 (6)

i.e., that the in?mum of I (T, r)/|T |2 is attained for S and ρ. By Lemma 1, we may always assume that |T ∩ B (r)| = |T \B (r)|. (7)

Consider a sequence {Ti , ri } such that |Ti | is a given value and I (Ti , ri ) approaches the in?mum. If {Ti } is unbounded then {ri } approaches in?nity by (7). For large ri , (7) yields that the area of the part of Ti outside of B (ri + 1) 1 2 is at least 4 |T |. If x is chosen from that part, then x2 ? ri > 2ri + 1, and hence I (Ti , ri ) tends to in?nity. We conclude that {Ti } and {ri } are bounded, and hence the in?mum of I (T, r)/|T |2 is attained.

6

Second, let S and ρ be chosen such that (6) holds. Denote by H the side of S not containing o and let m be the midpoint of H . Then S is symmetric (8)

with respect to the line connecting o and m. To show this, keep ρ ?xed and rotate the side H around m by an angle ?. Let S? be the triangle obtained in this way. Then |S? | = |S | + O(?2 ) and I (S? , ρ) = I (S, ρ) + ?I (S? , ρ) ?? · ? + O(?2 ).
?=0

Consequently, the minimality property of S yields ?I (S? , ρ) ?? This can be written as
l 0

= 0.
?=0

(9)

|(τ + a)2 ? s2 |τ dτ ?
0

l

|(τ ? a)2 ? s2 |τ dτ = 0

(10)

where 2l the length of H , a is the distance of m and the orthogonal projection of o to the a?ne hull a? H , and 2s is the length of a? H ∩ B (ρ). It follows from Lemma 1 that | a? H ∩ B (ρ)| < l. (11) We have to distinguish three cases. (i) H does not intersect B (ρ). Then, evaluating (10) gives 4al3 /3 = 0 and a = 0. (ii) H intersects B (ρ) exactly once. If a ≥ s, then (τ + a)2 ? s2 > |(τ ? a)2 ? s2 | holds for τ > 0. Thus (10) does not hold in this case. Therefore a < s or equivalently m ∈ int B (ρ). But this implies |H ∩ B (ρ)| > l which contradicts (11). So this case cannot occur. 7

(iii) H intersects B (ρ) twice, and hence |H ∩ B (ρ)| = 2s. Then evaluating (10) gives a(l3 ? 2s3 ) = 0. By (11), we know that l3 ? 2s3 = 0. Therefore a = 0. Thus in each case, a = 0 holds, which is in turn equivalent to (8). Finally, it follows from (8) that 1 I (S, ρ) = c(t)|S |2 . 2 Combined with (6) this proves the lemma. 2

Let t1 be the unique t, 0 < t < π/2, satisfying tan t = 2 t. Then for t < t1 the third side of T does not intersect B (ρ) and c(t) = 1 tan t 1 + ? . tan t 3 2t

c(t) attains a unique minimum at t0 , π/4 < t0 < π/3. We use the following properties of 1/c(t). LEMMA 4 1/c(t) is concave for t ≤ t1 , increasing for 0 < t ≤ t0 and decreasing for t0 ≤ t ≤ t1 . Proof: Derivating c(t) yields 1 tan2 t 1 2 + + 2? 2 tan t 3 2t 3 2 2 2 2 1 c (t) = + + tan t + tan3 t ? 3 . 3 tan t tan t 3 3 t c (t) = ? To show that 1/c(t) is concave, is equivalent to prove that c(t) c (t) ? 2c (t)2 > 0. We have c(t) c (t) ? 2c (t)2 = (tan t ? t)(3t ? 3 tan t + 3t tan2 t ? tan3 t) 3t3 tan3 t tan t 16 (t + 2 tan t + t tan2 t) + (1 + tan2 t) ? 9 3t2

It is not di?cult to see that 3t ? 3 tan t + 3t tan2 t ? tan3 t ≥ 0 8

for 0 ≤ t ≤ t1 . Thus, using tan t ≤ 2t, gives c(t) c (t) ? 2c (t)2 ≥ 16 tan t (1 + tan2 t) ? (5 + tan2 t) 9 3t 1 2 = (16 t + 16 t tan t ? 15 tan t ? 3 t tan2 t) > 0. 9t 2 LEMMA 5 Let f (t; π/k ) be the linear function representing the tangent to 1/c(t) at π/k . Then 1 π ≤ f t; c(t) k for 0 < t < π/2 and k = 3, 4, . . .. Proof: By Lemma 4, this holds for t ≤ t1 and it remains to be shown that c(t) ≥ 1 ) f (t; π 3 (12)

for t1 ≤ t < π/2. Let o, (h, 0) = (h(t), 0), and (h, l) = (h(t), l(t)) be the vertices of T = T (t) and denote by s the length of the intersection of B (ρ) and the side of T not containing o. Then Lemma 1 yields that s 1 ≤1? √ . l 2 For small ε > 0, we have I (T, ρ) ? I (T (t ? ε), ρ(t ? ε)) ≥ I (T, ρ) ? I (T (t ? ε), ρ). Note that as ε → 0,


(13)

(14)

|x ? ρ | dx =
T \T (t?ε) 0

2

2

h2 +l 2

|τ 2 ? ρ2 |τ dτ · ε + o(ε)

and |x2 ? ρ2 | dx =
T (t?ε)\T 0 l l

|h2 + u2 ? ρ2 | du · (h(t ? ε) ? h) + o(ε) |h2 + u2 ? ρ2 | du 9 h2 + l2 2l · ε + o(ε).

=
0

Thus the coe?cient of ε in the left hand side of (14) is
√ h2 +l 2

|τ ? ρ |τ dτ ?
0 0

2

2

l

h2 + l2 |h + u ? ρ | du 2l
2 2 2

=

2 4 4 s2 8 s3 1 2 s = ? + 4+ ? 3 +l4 ? 2 3 l l 3l 12 3 l
≥0

3

+

1 s 2 l

4

2 4 13 2 4 ≥ ? + 4+ ? l ≥1 3 l 24 3 where we used (13) and l2 (t) = 2 tan t ≥ 2 tan t1 = 4t1 . We deduce by (14) that I (T, ρ) ? I (T (t ? ε), ρ(t ? ε)) ≥ ε + o(ε), and hence c(t) ≥ c(t1 ) + (t ? t1 ). Finally, some simple calculations yield (12). LEMMA 6 t c(t) is monotonously increasing for t ≤ π/3. Proof: We have (tc(t)) = 3 tan t + tan3 t ? 2t tan2 t + t tan4 t ? 3t . 3 tan2 t 2



√ ≥13/24? 2/3

Since tan t ≥ t and the enumerator E (t) satis?es E (0) = 0 and E (t) = 4 tan2 t ? 4t tan t + 4 tan4 t + 4t tan5 t, we deduce that E (t) > 0 for 0 < t < π/3. 2

10

4

Proof of Theorem 3

Since, by the de?nition of c(t) and (5), I (Pk , ρk ) = c(π/k )/(2 k ), it follows from Lemma 6 that I (P3 , ρ3 ) > I (P4 , ρ4 ) > I (P5 , ρ5 ) > . . . . Therefore, if o ∈ int P , we have by Lemma 2 I (P, r) > 1.1 · I (P3 , ρ3 ) |P |2 > I (Pk , ρk ) |P |2 , i.e., the theorem holds in this case. So, let o ∈ int P and dissect P into triangles T1 , . . . , Tk with a common vertex o, and let 2 tj be the angle of Tj at o. By Lemma 3, we have
k

(15)

I (P, r) =
i=1

I (Ti , r) ≥

1 k c(ti ) |Ti |2 . 2 i=1

The Cauchy-Schwarz inequality yields 1 c(ti )|Ti | ≥ i=1 i=1 c(ti )
2 k k ?1 k 2

|Ti |
i=1

.

(16)

By Lemma 5,
k 1 π ≤ f ti ; k k=1 c(ti ) k=1 k

=

k . ) c( π k

Therefore, 1 I (P, r) ≥ 2 1 i=1 c(ti )
k ?1

|P |2 ≥

1 π c 2k k

|P |2 = I (Pk , ρk ) |P |2 ,

which proves the theorem.

5

Proof of Theorem 2

We can dissect every tile Qi into triangles such that we obtain a simplicial tiling with tiles T1 , . . . , Tk and at most n vertices. If we double each tile, we 11

may think of this as a polytope with f2 = 2k facets, f1 edges and f0 < 2n vertices. By Euler’s formula f2 ? f1 + f0 = 2 and f2 ≤ 2f0 ? 4 which implies k ≤ 2(n ? 2). (17)

Therefore, by Theorem 3, the inequality of quadratic and arithmetic means, and (17) we obtain
m i=1 Qi 2 |(x ? ai )2 ? ri | dx ≥ I (P3 , ρ3 ) i=1 k 2 k

|Ti |2 |Ti |
i=1

≥ I (P3 , ρ3 )

1 I (P3 , ρ3 ) ≥ , k 2(n ? 2)

which proves the theorem. To obtain the corollary, cover [0, 1]2 with k non-overlapping regular triangles of equal area |T |. Then, we obtain a Laguerre-tiling L with, say, n vertices by setting r2 = |T |/(2π ) for each tile. We have v (L) ≤ k I (P3 , ρ3 )|T |2 . Since we may choose the triangles such that k |T | → 1 and k/n → 2 as k → ∞, I (P3 , ρ3 ) lim sup n v (Lk ) ≤ , 2 n→∞ and by Theorem 2, we have ldel2 = I (P3 , ρ3 )/2.

6

Proof of Theorem 1

To every tile Qi with li sides we assign 2li rectangular triangles of area |Qi |/(2li ) and with angle π/li at the vertex o. Let k = 2 n i=1 li , let T1 , . . . , Tk be these triangles, and let tj denote the angle of Tj at o. Then k j =1 tj = 2πn. By Theorem 3,
Qi 2 |(x ? ai )2 ? ri | dx ≥ I (Pli , ρli )|Qi |2

and

n i=1 Qi 2 |(x ? ai )2 ? ri | dx ≥

k

c(tj )|Tj |2 .
j =1

12

By (16), we obtain from this
n i=1

1 ? 2 |(x ? ai )2 ? ri | dx ≥ c(tj )|Tj |2 ≥ ? Qi j =1 j =1 c(tj ) k ≤ 12(n ? 1).

k

?

k

??1 ? ?

k

?2

|Tj |? .

j =1

We have (18) This can be seen in the following way. If we double each tile Qi , we may think of this as a polytope with f0 vertices, f1 = 1/2 k edges and f2 = 2n facets. By Euler’s formula f2 ? f1 + f0 = 2 and f1 ≤ 3f2 ? 6, which implies (18). So, we obtain by Lemma 4, Jensen’s inequality, Lemma 6 and (18) 1 k = ≤ 1 k c( k j =1 tj ) j =1 c(tj ) Thus
n i=1 Qi k

2πn
2πn c( 2πn ) k k



12 n . c( π ) 6

|(x ? ai ) ?

2

2 ri | dx

c( π ) I (P6 , ρ6 ) , ≥ 6 = 12 n n

which proves the theorem. Corollary 1 follows as Corollary 2, except that the triangular tiling is replaced by the hexagonal tiling.

References
[1] Aurenhammer,F.: Power diagrams: properties, algorithms and applications. SIAM J. Comput. 16 (1987), 78 – 96 [2] Fejes T? oth,L.: Lagerungen in der Ebene, auf der Kugel und im Raum. 2nd ed. Springer-Verlag, Berlin 1972 [3] Gruber,P.M.: Volume approximation of convex bodies by inscribed polytopes. Math. Ann. 281 (1988), 229 – 245 [4] Gruber,P.M.: Volume approximation of convex bodies by circumscribed polytopes. The “Victor Klee Festschrift”, 309 – 317. DIMACS Ser. 4, Amer. Math. Soc. 1991 13

[5] Gruber,P.M.: Aspects of approximation of convex bodies. In: Handbook of convex geometry A, 319 – 345, North-Holland, Amsterdam 1993 [6] Gruber,P.M.: Asymptotic estimates for best and stepwise approximation of convex bodies II. Forum Math. 5 (1993), 521 – 538 [7] Ludwig,M.: Asymptotic approximation of smooth convex bodies by general polytopes. Manuscript [8] McClure,D.E., Vitale,R.A.: Polygonal approximation of plane convex bodies. J. Math. Anal. Appl. 51 (1975), 326 – 358
K? aroly B¨ or¨ oczky, Jr. Mathematical Institute of the Hungarian Academy of Sciences P.O. Box 127 H-1364 Budapest Monika Ludwig Technische Universit¨ at Wien Abteilung f¨ ur Analysis Wiedner Hauptstr. 8-10/1142 A-1040 Wien

14


赞助商链接

更多相关文章:
更多相关标签:

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图