The lower envelope is the boundary you see when looking at all lines from below. It's a piecewise linear function: each segment belongs to line. The lower envelope is concave because you're taking the pointwise minimum of linear functions. At each breakpoint, the slope decreases.
You'll hear this called the 'Convex Hull Trick' because the line segments trace a convex hull in the dual space. Lines on the envelope are sorted by slope, high to low from left to right. Adjacent lines intersect at breakpoints. For query , find which segment contains . That segment's line gives the minimum. The structure has at most segments.