Figure 5: Square of the length α.
Finally, summarizing, we have:
L(x, x) - L(x - α, x)+bε ≤
≤ U(x + α, x) - U(x, x) ≤
≤ U(x + α, x - α) - U(x,x - α) ≤
≤ U(x, x - α) - U(x - α, x - α)+bε
where, the first inequality comes from (20), the second one from (19) and the
last one from (22). So we obtain,
U (x, x - α) - U (x - α, x - α)+bε ≥ (x, x) - L(x - α, x)+bε. (23)
Subtracting b from both sides ends the proof. ■
The next lemma extends the property of submodularity of F form the small
square of length α to any square with two vertices on the diagonal.
Lemma 8.2 If Lemma 8.1 holds, then for any square with points in the diago-
nal, such as depicted in figure 7, we have,
F(z, x) - F(z, z) ≥ F(x, x) - F (x, z) .
Proof. (Lemma 8.2) Consider the square formed by the four points defined in
the lemma. Divide this square into rectangles such that their height is equal to
34