Why Most Lines Don't Matter

Suppose line $L_2$ is always above lines $L_1$ and $L_3$ in the range where queries happen. Then $L_2$ never wins. It's dominated. More precisely: if adding $L_2$ to the envelope would create a segment of zero width (the intersection with $L_1$ is to the right of intersection with $L_3$), then $L_2$ is useless.

This is the pruning rule. When adding a new line, remove any line that becomes dominated. Only $O(n)$ lines survive across the entire algorithm.