often use the notation oxx to denote the set Q of rectangles as
defined above as well as the vertices of these rectangles. There is
rarely any danger of confusion and where there is we shall be more
explicit. We shall use this notation in the proof of the lemma and
afterward.
Proof of Lemma. For each jeJ, denote R = [(s ,t ),(s',t)]. The
construction of Q is straightforward: we take o to be the set of all
the s. and s.,, ordered appropriately, and r to be the set of all
J J
t. and t.,, put in ascending order. We need to show that OxT is a
J J
refinement of P. Let, then, R. = [(s.,t.),(s',t')] be a rectangle in
P. Let a' be a partition of [s ,sj'] obtained by taking the points
from o between sj and s' (inclusive), and r' a partition of [t ,t']
obtained from T in the same manner. Then o'xT' is evidently a
partition of R.. I
J
Proposition 2.2.3. Let P,P' be two partitions of R. Then P and P'
have a common refinement, i.e., there exists a partition S of R that
is a refinement of both P and P'.
Proof. Let Q = oxx be a grid refining P (Lemma 2.2.2), and
Q' = o'xT' be a grid refining P'. Denote by p the partition of
[s,s'] formed by oo' (put in ascending order), Y the partition of
[t,t'] formed by putting Tr' in ascending order. Then S = pxY is a
common refinement of Q and Q', hence S refines P, and S refines P',
so S = pxY is our common refinement. (In fact, we have proved that
any two partitions have a common grid refinement.) I
For a given rectangle R, we can define an ordering on the class P
of partitions R as follows: we define P S Q for two partitions P,Q of