Line Envelope Convex Hull Trick

Query a lower line envelope while preserving parallel-line and intersection ties.

Line Envelope Convex Hull Trick

Concept Overview

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.

Worked Example

Consider the "Simple" lines indexed in their original order: line 0 is (2, 0) for y = 2x + 0, line 1 is (0, 1) for y = 0x + 1, and line 2 is (-1, 5) for y = -1x + 5. If we query the active prefix up to 3 lines at x = 1:

Lines:
0: y = 2x + 0
1: y = 0x + 1
2: y = -1x + 5

For Query x = 1:
Line 0: y = 2(1) + 0 = 2
Line 1: y = 0(1) + 1 = 1
Line 2: y = -1(1) + 5 = 4

The minimum value is 1, achieved by line 1.
Winning original index: 1
Distinct slopes: 3

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.

Limitations

This implementation assumes a static or offline set of lines that can be ordered by slope. It handles ties by choosing the smallest original index. For a fully dynamic set of lines where slopes are not monotonically ordered and lines can be added in any order, a more complex data structure like a dynamic Li Chao Tree or a dynamic convex hull trick utilizing a balanced binary search tree is required. It also only covers a finite discrete domain for the query coordinate rather than a general continuous solver.

References

The following external resources provide foundational knowledge, proofs, and extended techniques related to the Convex Hull Trick for dynamically computing the minimum or maximum values of a set of linear functions efficiently.

CP-Algorithms: Convex Hull Trick - Details the mathematical basis and algorithmic approach for constructing and querying line envelopes using the convex hull trick.

Line Envelope Convex Hull Trick