bb - Lower convex envelope/convex hull, Beneath-Beyond algorithm

Calling Sequence

[bbx,bby] = bb (X,Y)

Parameters

• X : column vector. A grid of points on which the function is sampled.
• Y : column vector. The value of the function on the grid X: usually Y(i)=f(X(i)) for some function f.
• bbx : column vector. X-coordinates of the vertices of the lower convex hull.
• bby : column vector. Y-coordinates of the vertices of the lower convex hull.

Description

Compute numerically the lower convex envelope of the set of points (X(i), Y(i)) and returns the coordinates of the vertices of the lower convex hull.

bb implements the Beneath-Beyond algorithm to achieve a linear-time algorithm.

Examples

    X=[-2:0.5:2]';
    Y=(X.^2-1)^2;
    [bbx,bby]=bb(X,Y);
    plot2d(X,Y,2,rect=[-3,-1,3,5]);
    plot(X,Y,'squareblue');
    plot(bbx,bby,'*red');
    plot2d(bbx,bby,5);
  

See Also

lft_llt,  

Author

Yves Lucet, University of British Columbia, BC, Canada

Bibliography