若w[a,c]+w[b,d] \(\leq\) w[b,c]+w[a,d] (a<b<c<d)

则w满足凸四边形不等式

若w[i,j] \(\leq\) w[i,j] ([i,j]\(\subseteq\) [i',j'])

则w满足区间单调

2D/1D:d[i,j]=opt{d[i,k-1]+d[k,j]}+w[i,j] (1 \(\leq\) i < k \(\leq\) j \(\leq\) n)

d满足凸四边形不等式 k[i,j-1] \(\leq\) k[i,j] \(\leq\) k[i+1,j]

w为凸 \(\Leftrightarrow\) w[i,j]+w[i+1,j+1] \(\leq\) w[i+1,j]+w[i,j+1]

1D/1D:f[i]=opt{f[j]+w[j,i]} (b[i] \(\leq\) j \(\leq\) i-1)

满足决策单调性，可用单调队列优化决策

[Dr.Lib]Note:Algorithms – 四边形不等式 by Liqueur Librazy is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.