Piecewise linear quadratic (plq), Convex hull (direct algorithm)
[plqco,iters] = plq_coDirect(plqf)
matrix. A plq function whose convex hull will be computed.
matrix. A plq function that is the convex hull of the original function.
Numerial Value. Number of iterations it took in computation
Computes the convex hull of a continuous, but not necessarily convex, plq function, where the input and output are given in the form of a plq matrix.
This algorithm performs a left-to-right plane sweep, examining two adjacent pieces at a time. It convexifies two pieces, and moves rightward, adding to the "current convex hull" to the left of the index, or backtracks if convexity was broken at a point. This algorithm runs in linear time, as each iteration either moves rightward, backtracks and merges two pieces, or backtracks without merging, but this can happen at most a linear number of times.
A special case is when three adjacent pieces are quadratic, linear, and quadratic, each quadratic piece contains the vertex of the quadratic, and a linear piece which is not the convex hull is between. To prevent cycling convergent behaviour, the linear piece is directly replaced with the convex hull of the two quadratic pieces.
// The hull of a linear-linear-quadratic function: plqf = [0,0,1,0;2,0,0,0;%inf,1,-4,4]; result = plq_coDirect(plqf), scf(); plq_plot(plqf, result); // The hull of a more complicated function: plqf =[-3,1,8,16;0,0,-1,-2;3,0,1,-2;%inf,1,-8,16]; result = plq_coDirect(plqf), scf(); plq_plot(plqf, result); | ![]() | ![]() |
Bryan Gardiner
, University of British Columbia, BC, Canada
_plq_conv_on_interval is used to ensure that pieces of a function are convex on an interval.