Integration Partitions and Grids

Video. Partitions and Grids Introduction

1. Definitions

Let sets in \({\mathbb R}^n\) of the form \(R = [a_1,b_1] \times \cdots \times [a_n , b_n]\) be called boxes (or simply rectangles). The volume of \(R\) is defined to equal the product of its side lengths, i.e.,

\[ |R| := \prod_{j=1}^n (b_j - a_j). \]

Two boxes \(R_1\) and \(R_2\) are called nonoverlapping when \(R_1 \cap R_2\) has no interior.

We say \(\mathcal P\) is a partition of box \(R \subset {\mathbb R}^n\) when \(\mathcal P\) is a finite set of pairwise nonoverlapping boxes contained in \(R\) whose union is \(R\).

A grid is a special partition \({\mathcal P}\) of \(R\) obtained by partitioning each interval \([a_1,b_1],\ldots,[a_n,b_n]\) by partitions \({\mathcal P}_1,\ldots,{\mathcal P}_n\), respectively and letting \(P\) consist of all possible products \(I_1 \times \cdots \times I_n\) where \(I_j \in {\mathcal P}_j\) for each \(j=1,\ldots,n\).

2. Refinements

Given two partitions \(\mathcal P\) and \(\mathcal P'\) of the same box \(R\), we say that \(\mathcal P'\) refines \(\mathcal P\) when every box \(R''\) in \({\mathcal P}'\) is entirely contained in some box \(R' \in {\mathcal P}\).

Theorem (Adapted Refinements)

Given any finite collection of boxes \(R_1,\ldots,R_N \subset {\mathbb R}^n\) contained in some box \(R\), There is a grid partition \(\mathcal G\) of \(R\) such that for each \(i \in \{1,\ldots,N\}\), the elements of \(\mathcal G\) which intersect the interior of \(R_i\) form a grid partition \({\mathcal G}_i\) of \(R_i\), i.e., they are nonoverlapping and have union equal exactly to \(R_i\).

Figure. A collection of boxes with tick marks indicating where boxes start and stop (left image) together with an adapted refinement (right image)

Proof

Meta (Main Idea)

Let \(R_0 := R = [a_1,b_1] \times \cdots \times [a_n,b_n]\). For each \(k = 1,\ldots,n\), let \(E_k\) be the set of real numbers which arise as endpoints of intervals formed from projecting any one of \(R_0,R_1,\ldots,R_N\) onto its \(k\)-th coordinate direction. In other words, if each \(R_i\) equals \([a^{(i)}_1,b^{(i)}_i] \times \cdots \times [a^{(i)}_n,b^{(i)}_n]\), then \(E_k\) is the set which contains \(a^{(0)}_k,b^{(0)}_k,\ldots,a^{(N)}_k,b^{(N)}_k\). The smallest element of \(E_k\) must be \(a_k\) and the largest must be \(b_k\).

For each \(k \in \{1,\ldots,n\}\), let \({\mathcal Q}_k\) be the partition of \([a_k,b_k]\) formed by the intervals between adjacent elements of \(E_k\), and let \(\mathcal G\) be the grid associated to these one-dimensional partitions. This \(\mathcal G\) is a partition of \(R\).

The elements of \(\mathcal G\) which intersect the interior of \(R_i := [a'_1,b'_1] \times \cdots \times [a'_n,b'_n]\) are precisely those for which their projection onto the \(k\)-th coordinate direction is an element of \({\mathcal Q}_k\) which is entirely contained in \([a'_k,b'_k]\); all such intervals partition \([a'_k,b'_k]\) and consequently all such boxes partition \(R_i\).

Corollary (Common Grid Refinements of Partitions)

Given any finite (positive) number of partitions \({\mathcal P}_1,\ldots,{\mathcal P}_N\), of \(R\), there is a grid partition \(\mathcal G\) of \(R\) which is a refinement of \({\mathcal P}_j\) for each \(j\). (As in the one-dimensional theory, we say that \(\mathcal G\) is a common refinement of \({\mathcal P}_1,\ldots,{\mathcal P}_N\).) Moreover, if \(R' \in {\mathcal P}_j\), then the elements of \(\mathcal G\) which overlap with \(R'\) form a grid partition of \(R'\).

Proof

Meta (Main Idea)

Apply the previous theorem to the collection of boxes formed by taking the union of all the \({\mathcal P}_i\).

3. Volume Equalities and Inequalities

Theorem (On Volumes)

If \(\mathcal P\) is a partition of the box \(R\), then
\[ |R| = \sum_{R' \in \mathcal P} |R'|. \]
If \(R_1,\ldots R_N\) are any boxes in \({\mathbb R}^n\) and if \(\mathcal G\) is a grid partition adapted to the boxes \(R_1,\ldots,R_N\) as above, then
\[ \mathop{\sum_{R' \in \mathcal G}}_{R' \subset \bigcup_j R_j} |R'| \leq \sum_{j=1}^N |R_j| \]
with equality if and only if the \(R_j\)'s are nonoverlapping.

Proof

Meta (Main Idea)

In one dimension, arrange the intervals \(I_j := [a_j,b_j]\), \(j \in \{1,\ldots,N\}\) contained in \(\mathcal P\) so that \(a_j\) is an increasing function of \(j\). If \(j < N\), it must be the case that \(a_{j+1} \geq b_j\) because \(a_{j+1}\) is already greater than or equal to \(a_j\) but \(I_{j+1}\) has no interior overlap with \(I_j\). If \(a_{j+1}\) were strictly greater than \(b_j\), then the points inside \((b_j,a_{j+1})\) would not be contained in any element of the partition. Thus the intervals are end-to-end as expected, and the sum \(\sum_{j=1}^n (b_j - a_j)\) telescopes to equal \(b_{N} - a_1\). By a similar argument to that above, \(a_1\) must be the left endpoint of the original interval partitioned by \(\mathcal P\) and \(b_N\) must be the right endpoint.
If \(\mathcal G\) is a grid partition of \(R := [a_1,b_1] \times \cdots \times [a_n,b_n]\), then the 1D result guarantees that
\[ \begin{aligned} \sum_{R' \in \mathcal G} |R'| & = \sum_{I_1 \in {\mathcal P_1}} \cdots \sum_{I_n \in {\mathcal P_n}} |I_1| \cdots |I_n| \\ & = \prod_{j=1}^n \sum_{I_j \in {\mathcal P_j}} |I_j| = |R|.\end{aligned}\]
In general, refine \(\mathcal P\) by a grid \(\mathcal G\). Then
\[{}|R|{}\]
\[{}= \sum_{R'' \in {\mathcal G}} |R''|{}\]
\[{}= \sum_{R' \in \mathcal P} \mathop{\sum_{R'' \in \mathcal G}}_{R'' \subset R'} |R''|{}\]
\[{}= \sum_{R' \in \mathcal P} |R'|{}\]
because we have grids of \(R\) and \(R'\), respectively.
For the inequality, note that
\[{}\mathop{\sum_{R' \in \mathcal G}}_{R' \subset \bigcup_j R_j} |R'|{}\]
\[{}\leq \sum_{j=1}^N \mathop{\sum_{R' \in \mathcal G}}_{R' \subset R_j} |R'|{}\]
\[{}= \sum_{j=1}^N |R_j|.{}\]

Equality will hold if and only if each \(R'\) is contained in only one of the \(R_j\), which will happen exactly when the \(R_j\) are nonoverlapping.

4. Approximate Cubes

Meta (Sometimes the Shape Matters)

In some circumstances, it is helpful to work exclusively with partitions whose elements are uniform (i.e., not wildly different sizes in different directions). The simplest scenario would be when all the elements of the partition are cubes (equal side lengths in all directions) of equal size. That's not always possible, but it is always possible to work with partitions which are not too distorted relative to cubes.

We will call a set \(R := [a_1,b_1] \times \cdots \times [a_n,b_n]\) an approximate cube of side length \(\delta > 0\) when \(\delta \leq b_k - a_k \leq 2 \delta\) for each \(k \in \{1,\ldots,n\}\).

Theorem (Refining with Approximate Cubes)

Given any grid partition \(\mathcal G\) of a rectangle \(R\), it has a refinement \({\mathcal G}'\), also a grid partition such that there is some \(\delta > 0\) for which every \(R' \in {\mathcal G}'\) is an approximate cube of side length \(\delta\).

Proof

Meta (Main Idea)

Let \(\delta\) be the length of the shortest interval appearing in any of the one-dimensional partitions \({\mathcal Q}_1,\ldots,{\mathcal Q}_n\) forming \(\mathcal G\). Refine each of these partitions by subdividing any interval of length \(\ell \geq \delta\) into \(\lfloor \ell \delta^{-1} \rfloor - 1\) intervals of exactly length \(\delta\) and a remainder at the end. The length of the remainder is \(\ell - \delta (\lfloor \ell \delta^{-1} \rfloor - 1 )\), which is between \(\ell - \delta (\ell \delta^{-1}-2) = 2 \delta\) and \(\ell - \delta(\ell \delta^{-1} - 1) = \delta\).

Exercise

Suppose that \(R_0\) is any cube and \(\mathcal P\) is any partition of it. Show that there is a constant \(C\) depending only on \(R_0\) and \(\mathcal P\) such that every grid partition \(\mathcal G\) of \(R_0\) admits some partition \(\mathcal{P}'\) of \(R_0\) which is a common refinement of \(\mathcal P\) and \(\mathcal G\) such that

\[ \sum_{R \in \mathcal G \setminus \mathcal{P}'} |R| = \sum_{R' \in \mathcal{P}' \setminus \mathcal G} |R'| \leq C || \mathcal{G}|| \]

where \(||\mathcal{G}||\) is the diameter of the largest box in \(\mathcal{G}\).

Hint

Use the common grid refinement of \(\mathcal{P}\) and \(\mathcal{G}\) and prove a bound on the sum of the volumes of the boxes of \(\mathcal{G}\) which get subdivided in this procedure. This is analogous to an argument appearing in the proof of equivalence of Riemann and Darboux integrals.