§ Monge Matrix
- Suppose we two line segments
- 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 @
- 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
D=1 (since those are the indexes of the points on the two line segments), we get
dist + dist > dist + dist
- 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 ]
- Suppose we have a dp . That is, we need to find row minima for each row in a 2D matrix.
- Now assume that has ascending row minima