pl_bb

Lower convex envelope/convex hull, Beneath-Beyond algorithm

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

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.

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.

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

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

Yves Lucet, University of British Columbia, BC, Canada

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

<< CCA