Deque Operations - Walkthrough

Lines: $y = 3x + 10$, $y = 2x + 15$, $y = x + 22$. Slopes are decreasing (sorted). Build the lower envelope. Add line 1 ($3x+10$): deque = [L1]. Add line 2 ($2x+15$): check if L1 is still useful.

Intersection at $x = 5$. L2 better for $x > 5$. Deque = [L1, L2]. Add line 3 ($x+22$): L3 intersects L2 at $x = 7$. L3 intersects L1 at $x = 6$. L2 is not dominated ($6 > 5$). Final deque = [L1, L2, L3]. Query $x = 4$: L1 gives $22$, L3 gives $26$. Min = 22 from L1. Deque structure gives $O(1)$ amortized query.