The Quadrangle Inequality

$w(a,c) + w(b,d) \le w(a,d) + w(b,c)$ for all $a \le b \le c \le d$: crossing costs no more than containing. With interval monotonicity it narrows the split range by a constant factor, cutting interval DP from $O(n^3)$ to $O(n^2 \log n)$.

$w(a,c) + w(b,d) \le w(a,d) + w(b,c)$ for all $a \le b \le c \le d$: crossing costs no more than containing. With interval monotonicity it forces the optimal split point to be monotone, cutting interval DP from $O(n^3)$ to $O(n^2)$.

$w(a,c) + w(b,d) \ge w(a,d) + w(b,c)$ for all $a \le b \le c \le d$: containing costs no more than crossing. With interval monotonicity it forces the optimal split point to be monotone, cutting interval DP from $O(n^3)$ to $O(n^2)$.

$w(a,b) + w(c,d) \le w(a,c) + w(b,d)$ for all $a \le b \le c \le d$: disjoint costs no more than overlapping. With interval monotonicity it forces the optimal split point to be monotone, cutting interval DP from $O(n^3)$ to $O(n^2)$.