Name

pl_bb — Lower convex envelope/convex hull, Beneath-Beyond algorithm

Calling Sequence

[bbx,bby] = pl_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

<listitem>

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.

</listitem>
<listitem>

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

</listitem>

Examples

    X=[-2:0.5:2]';
    Y=(X.^2-1)^2;
    [bbx,bby]=pl_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

pl_lft_llt

Authors

Yves Lucet, University of British Columbia, BC, Canada

Bibliography

Preparata, Franco P., Shamos, Michael I., Computational Geometry An Introduction, Series: Monographs in Computer Science, 1st ed. 1985. Corr. 5th printing 1993.