§ Monge Matrix

• Suppose we two line segments AB, CD:

A   C
@   @
@   @
@   @
B   D

• What is the relationship between the lengths |AC| + |BD| (straight lines) versus |AC| + |BD| (diagonals)?
• Draw the diagonal, label the point of intersection of diagonals as I.

A---C
@\ /@
@ I @
@/ \@
B---D

• By triangle inequality, we have that AI + IC > AC and BI + ID > BD. Adding these up, we get (AI + IC) + (BI + ID) > AC + BD.
• Rearranging we get (AI + ID) + (BI + IC) > AC + BD, which is equal to AD + BC > AC + BD.
• So, the sum of lengths between opposite points is greater than sum of lengths between non-opposite points .
• If we think of this as a matrix dist[A/B][C/D], we have that dist[a][d] + dist[b][c] > dist[a][c] + dist[b][d].
• If we replace A=0, B=1, C=0, D=1 (since those are the indexes of the points on the two line segments), we get dist[0][1] + dist[1][0] > dist[0][0] + dist[1][1]
• If we generalize to sets of points on a line, let's have the indexes i, j. Then the condition would read dist[i][j] + dist[j][i] > dist[i][i] + dist[j][j].
• A matrix dist[.][.] which obeys this condition is said to be a Monge Matrix .

§ Theorem: Monge matrices are totally monotone

§ Theorem: totally monotone matrices have ascending row minima

§ 1D 1D DP [TODO ]

• https://robert1003.github.io/2020/02/29/dp-opt-knuth.html
• Suppose we have a dp $dp[r] = \min_{0 \leq l \leq r} f(l, r)$. That is, we need to find row minima for each row $r$ in a 2D matrix.
• Now assume that $f(l, r)$ has ascending row minima