How can I calculate the convex envelope of a function?

I'd like to calculate the convex envelope of a function f: . I know that in MATLAB I can use K = convhull(X,Y) to calculate the convex hull of the points (X;Y).

Therefore, I was thinking of using the relation between "convex hulls of a set - epigraph of a function - convex envelope of a function". I've read that . But I don't know how to use this connection and obtain .

Otherwise, I was thinking of using the Legendre transformation twice but I wouldn't know where to start.

However, I need the concave envolope of a function so I was wondering if there is a direct method to calculate it (without using the concave hull of its epigraph).

[Yu Lan]

Did you solve this problem? I have the same problem as you met.

[Tsiry Avisoa Randrianasolo]

Did you solve your problem? Here is my suggestion. You have to distinguish between the segments that look upward (for the convex envelop) and downward (for the concave envelope).

x = linspace(-2*pi, 2*pi)';
y = x.*sin(x);

P = [x, y];
k = convhull(P);

low = [true;  diff(P(k,1))>=0];% lower convex envelope
up = [diff(P(k,1))<=0; true];% upper convex envelope

plot(x, y,'*')
hold on
plot(P(k(low), 1), P(k(low), 2),'r');
plot(P(k(up), 1), P(k(up), 2),'g');
legend('y', 'convex envelope', 'concave envelope', 'location', 'best' )
hold off