Line Envelope Convex Hull Trick
Query a lower line envelope while preserving parallel-line and intersection ties.
Free theory articleQuery a lower line envelope while preserving parallel-line and intersection ties.
Concept & interpretation
The Convex Hull Trick for affine lower (or upper) envelopes is an algorithm useful in dynamic programming and computational geometry to efficiently query the minimum value of a set of linear functions at any given x-coordinate. It operates by maintaining the convex hull of the lines. By ordering the lines by slope, the algorithm discards dominated lines and intersecting segments, thereby answering min(a*x+b) queries optimally.
Experiment
You can interact with the Line Envelope Convex Hull Trick module to explore how the lower envelope is formed and queried. Here are the steps to actuate the native controls using their exact labels:
- Set Lines to "Simple", "Parallel", or "Duplicate" to choose the dataset.
- Set Active prefix to 0, 1, 2, or 3 to observe how introducing lines updates the envelope.
- Set Query x to evaluate the minimum value across the active lines at the chosen x coordinate.