me_pe2d - 2D Moreau envelope, PE algorithm
Compute numerically the discrete Moreau envelope of a set of spatial points (X(i1,i2),f(i1,i2)) at slopes (X(j1,j2)). It reduces computation to one dimension, and uses the one-dimensional parabolic envelope algorithm (see me_pe) resulting in a theta(n*m) linear-time algorithm.
function f=f(lambda,x),f=lambda * x.^2,endfunction function g=g(lambda1,lambda2,x,y),g=f(lambda1,x)+f(lambda2,y),endfunction lambda1=1;lambda2=2; x1=(-10:10)';x2=(-5:5)'; [X, Y]=ndgrid(x1,x2);F=g(lambda1,lambda2,X,Y); s1=(-4:4)';s2=(-5:6)'; Xr=x1;Xc=x2;Sr=s1;Sc=s2; desired=me_pe2d(x1,x2,F,s1,s2); //1d computation for separable function Ms1=me_direct(x1,f(lambda1,x1),s1); Ms2=me_direct(x2,f(lambda2,x2),s2); t1 = Ms1 * ones(1,size(Ms2,1)); t2 = ones(size(Ms1,1),1) * Ms2'; correct=t1+t2; b = and(correct == desired);
me_brute2d, me_direct2d, me_llt2d, me_nep2d, me_pe,
Yves Lucet, University of British Columbia, BC, Canada