• Constraints are added one by one. The algorithm keeps the optimal solution (vertex v_i) of the intermediate, relaxed, problem.

• C_i denotes the intersection of i half-planes h₁, h₂, ..., h_i,  i=2,3,...,n.

•  v_i-1  in h_i ==> v_i =v_i-1
• v_i-1  not in  h_i ==> either C_i is empty or v_i is on the line l_i bounding h_i. Proof

• Vertex v_i can be found in O(i) time by determining intersections of l_i with l_j, j=1,2, ...,i-1. The highest intersection bounding from below yields v_i.

• Incremental algorithm requires O(n²) time and O(n) space.

NEXT PAGE