<?xml version="1.0" encoding="ISO-8859-1"?><refentry xmlns="http://docbook.org/ns/docbook" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:svg="http://www.w3.org/2000/svg" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:db="http://docbook.org/ns/docbook" version="5.0-subset Scilab" xml:lang="en" xml:id="pl_me_pe"><info><pubdate>04-Apr-2006</pubdate></info><refnamediv><refname>pl_me_pe</refname><refpurpose>Moreau envelope, Parabolic Envelope algorithm</refpurpose></refnamediv>
  
   
  
   
  
   
  
   
  
   

  
   <refsynopsisdiv><title>Calling Sequence</title><synopsis>M = pl_me_pe(x0,xn,f)</synopsis></refsynopsisdiv>

  
   <refsection><title>Parameters</title>
  
      <variablelist>

    
         <varlistentry>
    
            <term>x0</term>
    
            <listitem>
       
               <para>real number. Lower bound of the interval.
       </para>
    
            </listitem>
    
         </varlistentry>

    
         <varlistentry>
    
            <term>xn</term>
    
            <listitem>
       
               <para>real number. Upper bound of the interval.
       </para>
    
            </listitem>
    
         </varlistentry>

    
         <varlistentry>
    
            <term>f</term>
    
            <listitem>
       
               <para>column vector. The value of the function on the grid
    X=(x0:h:xn)'; where n=length(f), and h=(xn-x0)/(n-1); so f(i)=fu(X(i)) for some function fu.
       </para>
    
            </listitem>
    
         </varlistentry>

    
         <varlistentry>
    
            <term>M</term>
    
            <listitem>
       
               <para>column vector. Contains the value of the Moreau envelope M of the function f evaluated on at the points S(j). In other words: M(j) = Min(||S(j) - X(i)||^2 + f(i) | over all indexes i)
       </para>
    
            </listitem>
    
         </varlistentry>
  
      </variablelist>
  
   </refsection>
 
  
   <refsection><title>Description</title>
     
         <para>
	Compute numerically the discrete Moreau envelope of a set of planar points (X(i),f(i)) at slopes S(j)=X(j), i.e. <!--<programlisting><![CDATA[
                                          2
       M(j) = min f(i) + || s(j) - x(i) ||.
               i
]]></programlisting>-->
			<para>
				<inlinemediaobject>
					<imageobject>
						<imagedata fileref="pl_ImagesOfEquationsByLatex/pl_me_pe/pl_me_pe_1.png"/>
					</imageobject>
				</inlinemediaobject>
			</para>
	<para>It reduces computation to a 1,..,n grid with</para> <!--<programlisting><![CDATA[
           2               2                    2
    M(j)= h * min [ ||j-i|| + f(x_0 + i * h) / h  ]
               i
]]></programlisting>-->
			<para>
				<inlinemediaobject>
					<imageobject>
						<imagedata fileref="pl_ImagesOfEquationsByLatex/pl_me_pe/pl_me_pe_2.png"/>
					</imageobject>
				</inlinemediaobject>
			</para>
        
         
	
         <para>
	The algorithms runs in linear time Theta(n) with
	n=length(X)=length(f) by computing the lower parabolic envelope (PE).
	</para>
	</para>
     
   </refsection>

  
   <refsection><title>Examples</title><programlisting role="example"><![CDATA[
    X=[-5:0.5:5]';
    Y=X.^2;
    M=pl_me_pe(-5,5,Y)
]]></programlisting></refsection>

  
   <refsection><title>See Also</title><simplelist type="inline">
    
      <member> 
         <link linkend="pl_me_pe_2d">pl_me_pe_2d</link> 
      </member>
    
      <member> 
         <link linkend="pl_me_direct">pl_me_direct</link> 
      </member>
    
      <member> 
         <link linkend="pl_me_llt">pl_me_llt</link> 
      </member>
    
      <member> 
         <link linkend="pl_me_nep">pl_me_nep</link> 
      </member>
  
   </simplelist></refsection>

  
   <refsection><title>Authors</title><para>
	  
      <literal>Yves Lucet</literal>, University of British Columbia, BC, Canada
  </para></refsection>

  
   <refsection><title>Bibliography</title>

   <itemizedlist>
      <listitem>
        Y. Lucet, 2007, Fast Moreau Envelope Computation I: Numerical Algorithms, Numerical Algorithms, 43(3):235-249.
      </listitem>
      <listitem>
        P. F. Felzenszwalb and D. P. Huttenlocher, 2004, Distance transforms of sampled functions, Tech. Rep. TR2004-1963,
		Cornell Computing and Information Science.
      </listitem>
   </itemizedlist>
  
   </refsection>

</refentry>
