122 1. Measure theory In the one-dimensional case, this estimate was established via the rising sun lemma. Unfortunately, that lemma relied heavily on the ordered nature of R, and does not have an obvious analogue in higher dimensions. Instead, we will use the following covering lemma. Given an open ball B = B(x, r) in Rd and a real number c 0, we write cB := B(x, cr) for the ball with the same center as B, but c times the radius. (Note that this is slightly different from the set c · B := {cy : y ∈ B}—why?) Note that |cB| = cd|B| for any open ball B ⊂ Rd and any c 0. Lemma 1.6.22 (Vitali-type covering lemma). Let B1,...,Bn be a finite collection of open balls in Rd (not necessarily disjoint). Then there exists a subcollection B1,...,Bm of disjoint balls in this collection, such that (1.27) n i=1 Bi ⊂ m j=1 3Bj. In particular, by finite subadditivity, m( n i=1 Bi) ≤ 3d m j=1 m(Bj). Proof. We use a greedy algorithm argument, selecting the balls Bi to be as large as possible while remaining disjoint. More precisely, we run the following algorithm: Step 0. Initialise m = 0 (so that, initially, there are no balls B1,...,Bm in the desired collection). Step 1. Consider all the balls Bj that do not already intersect one of the B1,...,Bm (so, initially, all of the balls B1,...,Bn will be consid- ered). If there are no such balls, STOP. Otherwise, go on to Step 2. Step 2. Locate the largest ball Bj that does not already intersect one of the B1,...,Bm. (If there are multiple largest balls with exactly the same radius, break the tie arbitrarily.) Add this ball to the col- lection B1,...,Bm by setting Bm+1 := Bj and then incrementing m to m + 1. Then return to Step 1. Note that at each iteration of this algorithm, the number of available balls amongst the B1,...,Bn drops by at least one (since each ball selected certainly intersects itself and so cannot be selected again). So this algo- rithm terminates in finite time. It is also clear from construction that the B1,...,Bm are a subcollection of the B1,...,Bn consisting of disjoint balls. So the only task remaining is to verify that (1.27) holds at the completion of the algorithm, i.e., to show that each ball Bi in the original collection is covered by the triples 3Bj of the subcollection.

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2011 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.