Li Chao Versus Hull

Freedom from convexity. The plain hull needs the minimized family to be lines with a convex envelope; a Li Chao tree takes arbitrary functions that may cross any number of times, answers queries in any order, and accepts them restricted to a subinterval.

Freedom from ordering. The plain hull needs slopes inserted in monotone order and often queries in monotone order too; a Li Chao tree takes lines in any order, answers queries in any order, and accepts lines restricted to a subinterval.

Freedom from ordering. The plain hull needs slopes inserted in monotone order and often queries in monotone order too; a Li Chao tree takes lines in any order, answers queries in any order, and deletes a line that is already inserted.

A better asymptotic. The plain hull answers a query in $O(\log n)$ and inserts in $O(\log n)$ too; a Li Chao tree answers queries in $O(1)$, inserts lines in $O(1)$, and accepts lines restricted to a subinterval.