Vocabulary - Quadrangle Inequality

The quadrangle inequality (QI) is a condition on cost functions. For indices $a \leq b \leq c \leq d$: $cost(a, c) + cost(b, d) \leq cost(a, d) + cost(b, c)$ Picture four points on a line.

The left side adds costs of two overlapping intervals $[a,c]$ and $[b,d]$ that share $[b,c]$. The right side adds the full span $[a,d]$ plus the overlap $[b,c]$. QI says: overlapping intervals cost no more than span-plus-overlap. When cost satisfies QI, optimal splits become monotonic. Without QI, you'd search all possibilities. With QI, you can prune.