Adding a New Line

When adding line $L_{new}$ with slope $m_{new}$:

$1.$ While the deque has $\geq 2$ lines, check if the last line is now dominated.

$2.$ Let $L_1$ be second-to-last, $L_2$ be last. If $L_2$ loses to both $L_1$ and $L_{new}$ everywhere between their intersections, pop $L_2$.

$3.$ Formally: if $intersect(L_1, L_{new}) \leq intersect(L_1, L_2)$, then $L_2$ is useless. Pop it.

$4.$ Push $L_{new}$. This maintains the lower envelope invariant.