1679
правок
Изменения
м
Нет описания правки
| definition=
Функция a удовлетворяет '''неравенству четырехугольника(quadrangle inequation)''', если
: <tex>\forall i \leq le i' \leq le j \leq le j' : a[i][j] + a[i'][j'] \leq le a[i'][j] + a[i][j']</tex>
}}
| definition=
Функция a является '''монотонной(monotone)''', если
: <tex>\forall i \leq le i' < j \leq le j' : a[i][j'] \leq le a[i'][j] </tex>
}}
| proof=
Заметим, что <tex> w[i][j] = w[i][t] + w[t+1][j] </tex>, так как <tex> w[i][j] </tex> - простая арифметическая сумма. Тогда:
: <tex> w[i][j] + w[i'][j'] \leq le w[i'][j] + w[i][j']</tex>: <tex> (w[i][i' - 1] + w[i'][j]) + (w[i'][j] + w[j + 1][j']) \leq le (w[i'][j]) + (w[i][i' - 1] + w[i'][j] + w[j + 1][j']) </tex>
Получили <tex> 0 \leq 0 </tex>, что является верным. Лемма доказана.
}}
Рассмотрим два случая:
# <tex> i' = j</tex>#: <tex> i < i' = j < j'</tex>. Тогда неравенство четырехугольника сводится к:#: <tex> D[i][j] + D[j][j'] \leq le D[i][j']</tex>#: Пусть <tex> k = R[i][j']</tex>. Получили два симметричных случая:## <tex> k \leq le j</tex>##:: <tex> D[i][j] + D[j][j'] \leq le w[i][j] + D[i][k-1] + D[k][j] + D{[j][j'] </tex> - по определению <tex> D[i][j].</tex>:##: <= tex> \le w[i][j'] + D[i][k-1] + D[k][j] + D{[j][j'] </tex> - по монотонности w:##: <= tex> \le w[i][j'] + D[i][k-1] + D[k][j'] </tex> - по предположению индукции:##: <= tex> \le D[i][j'] </tex> - по определению <tex> D[i][j']</tex>## <tex> k \geq ge j </tex> - аналогичный предыдущему случай.# <tex> i' < j</tex>#: <tex> i < i' < j < j'</tex> #: Пусть <tex> y = R[i'][j] </tex> и <tex> z = R[i][j]</tex>. Получили два различных симметричных случая:## <tex> z \leq le y или z \geq y. Рассмотрим первый из них.</tex>##: Получили z \leq le y \leq le j (по определению y) и i < z(по определению z). Получим: ##: <tex> D[i'][j'] + D[i][j] \leq le D_y[i'][j'] + D_z[i][j] = w[i'][j'] + D[i'][y-1] + D[y][j'] + w[i][j] + D[i][z-1] + D[z][j]</tex>##: <tex> \leq le w[i][j'] + w[i'][j] + D[i'][y-1] + D[i][z-1] + D[z][j] + D[y][j'] </tex> - по неравенству четырехугольника для <tex> w</tex>##: <tex> \leq le w[i][j'] + w[i'][j] + D[i'][y-1] + D[i][z-1] + D[y][j] + D[z][j'] </tex> - по индукционному предположению##: <tex> = (w[i][j'] + D[i][z-1] + D[z][j']) + (w[i'][j] + D[i'][y-1] + D[y][j]) </tex> //переставить нормально##: <tex> \leq le D[i][j'] + D[i'][j] </tex> - по определению D.## <tex> z \ge y </tex> доказывается аналогично
Индукционный шаг завершен, лемма доказана.
}}
Монотонность точки разреза
| statement=
<tex> R[i][j - 1] \leq le R[i][j] \leq le R[i + 1][j] </tex>
| proof=
Для доказательства этого сперва докажем несколько лемм:
}}
