<< plq_co | plq | plq_coSplit >>

CCA (Computational Convex Analysis) >> plq > plq_coDirect

# plq_coDirect

Piecewise linear quadratic (plq), Convex hull (direct algorithm)

### Calling Sequence

    plqco = plq_coDirect(plqf)

### Parameters

plqf

  matrix. A plq function whose convex hull will be computed.

plqco

  matrix. A plq function that is the convex hull of the original function.

### Description

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.

### Examples

    // 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);

### See Also

- plq_co
- plq_coSplit
- plq_function

### Authors

`Bryan Gardiner`, University of British Columbia, BC, Canada

### Used Functions

_plq_conv_on_interval is used to ensure that pieces of a function are convex on an interval.

<< plq_co | plq | plq_coSplit >>