#Monge性（全単調性）とは
- 定義
- $m$行$n$列の実数値行列$A=(a(i,j))$がMonge性（全単調性）を持つとは、 任意の$1\leqq s\leqq t\leqq m$, $1\leqq k\leqq l\leqq n$にたいして、$a(s,k)+a(t,l) < a(s,l)+a(t,k)$を満たすことをいう
これは三角不等式になぞらえて、四角不等式とも呼ばれます。
さて、より詳しく理解するために行列で考えていきましょう。以下のような2行2列の行列を考えます。
\begin{bmatrix}
a & b \\
c & d
\end{bmatrix}
この時、$a+d \leqq b+c$であれば、この行列は単調であるといいます。
これを拡張し、任意の行列$A$に対して、どのように部分行列を選んでも単調であること場合に、$A$はMonge（全単調）行列といいます。
そこまで難しくありませんね。
#Monge性の応用
##SMAWK algorithm
Monge性の応用として最も有名なものに、高速な行列探索法として知られる_SMAWK algorithm（Aggarwal-Klawe-Moran-Shor-Wilbur 87）_というものがあります。
これは、行最小値発見問題を線形時間で解くアルゴリズムとして1987年に発表されたものです。この著者たちはものごっつい有名な方々なのでぜひ調べてみてください。
- 行最小値発見問題
- $n$行$m$列$（m>n）$の行列が与えられたとき、各行の最小値を求めよ
参考書によっては最大値を扱うものもありますが、どちらの場合も同じアルゴリズムで解くことができます。（Monge性の不等式の不等号が反転しますが...）
詳しいアルゴリズムは元論文：Geometric applications of a matrix-searching algorithm をご覧ください。
##DAG（有向非閉路グラフ）への応用
計算幾何学における有名な問題の1つに、凸$n$角形の最適$k$角形近似問題$（k<n）$があります。
この問題は、凸$n$角形の各頂点をグラフのノードとすることでDAGの$k-$リンク最大重み経路問題に帰着することができます。
Monge性を持つDAGにおいて、最大重み経路は$O(n)$で計算できることが知られています。
これを、$k$個のリンクを持つ経路に拡張するために、パラメトリック探索という探索方法が用いられます。
より詳しい理解を得たい方は、こちらの論文：
Finding a Minimum-Weight k-Link Path in Graphs with the Concave Monge Property and Applications を参照ください。
この他、競技プログラミングなんかでもMongeDPを用いることで高速化を図るなんてことが多いみたいです。
#参考文献