Laplace Operator

Let M=(V,E,F) be an oriented triangulated surface without boundary and p:VR3 a realization. In earlier lectures we considered the space of piecewise linear functions on M:
WPL:={f~:MR|f~|σ is affine for all σF}.
A basis of WPL is given by : ϕiWPL defined by ϕi(pj)=δij, an  interpolation map is defined by:
intPL:RVWPL,ff~=iVfiϕi.

graph phi

The graph of ϕi

For some purposes piecewise constant function are more convenient then piecewise linear ones, therefore, we introduce a new function space on M that consists of piecewise constant functions. In order to do that we assign a domain to each vertex:
For every edge eijE the center is given by Sij=12(pi+pj) analog  for every triangle σ={i,j,k}F the center of mass is defined as Sijk=13(pi+pj+pk).

trianglemasscenter

If we connect the center of the edges with the center of mass the triangle is divided into three parts with equal area. Now we can assign to each vertex pi the parts of the adjacent triangles that contain pi and denote it with Di.

pointarea

The domain Di (gray colored) associated to the vertex pi

For the area of Di we obtain:
Ai:=13σ={i,j,k}FAσ.

The space of piecewise constant functions is defined in the following way:
WPC:={f^:MR|f^|Di is constant for all iV}.
Also on WPC we have a canonical basis ΨiWPC defined by Ψi(pj)=δij and an interpolation map:
intPC:RVWPC,ff^=iVfiΨi.

graph psi

Graph of Ψi

There is a similar construction that assigns to each vertex an face and works purely combinatorial: For a triangulated M surface one can define its discrete dual surface M=(V,E,F). The faces of M correspond to the vertices of M and the vertices of M to the faces of M. The set of edges stays the same. Two vertices in M are connected by  an edge if the corresponding faces in M are adjacent. For more informations see here.

dualsurface

A piece of an triangulated surface M and its dual M. The red vertices and edges belong to M and the blues ones to M.

Since in general it is not easy to compute the area of the dual faces with the metric of the original one, we used the above construction of the Di’s to define WPC. On WPL we defined the usual scalar product f~,g~PL:=Mf~g~ and computed the matrix B representing it with respect to the basis {ϕ1,ϕN}, i.e. bij:=ϕi,ϕjPL. This gave us a scalar product on RV:

f,gPL=ftBg=i,jVfigjbij.

On the same way we define an scalarproduct on WPC:
,PC:WPC×WPCR,f^,g^PC:=Mf^g^.
The matrix A representing it with respect to the basis  {Ψ1,ΨN} is a diagonal matrix since:
aij:=Ψi,ΨjPC =MΨiΨj=Aiδij.
This gives us a new  scalar product on RV:
f,gPC:=ftAg=iVfigiaii.
Note that the basis {Ψ1,ΨN} is orthogonal with respect to ,PC, while the same is not true for {ϕ1,ϕN} with respect to ,PL.
Now we have two scalar products on RV one represented by a symmetric positive definite matrix B and one by a positive definite diagonal one A.
Our aim is to define a discrete laplace operator Δ:RVRV analog to the smooth laplacian we discussed earlier. We will see that the discrtelaplacian depends on the choice of scalarproduct.
On a smooth surface M we have:
Δf,g=MΔfg=Mgradf,gradg.
This identity should also be true in the discrete case and will serve us as definition for the discrete laplacian. We already defined the bilinear operator
L:RV×RVR,f,gMgradf,gradg,

and discussed the relation between  quadratic forms, symmetric bilinear maps and maps between dual spaces ( lecture: dirichlet energy 2 ).
WPLEDWPLinterpol.interpol.RVLRV
In the finite case the quadratic form, bilinear form and map between the dual spaces can all be represented by the same matrix L .

For f,gRV we have:
ftLg=Mgradf,gradg=!MΔfg=Δf,g.
This gives us one laplace operator for each scalarproduct on RV:
ftLg={(ΔPLf)tBg,(ΔPCf)tAg,{ΔPL=(LB1)t=B1L,ΔPC=(LA1)t=A1L.

In general it is complicated and expensive to compute B1, such that it is much easier to use ΔPC instead of ΔPL. Witch of the laplacians one has to choose depends on the nature of the problem.

One famous problem form physics and geometry is the Poisson problem:
Given ρRV find uRV such that:
Δu=ρ.
For Poisson problems both laplacians can be used since:

ΔPLu=(LB1)tu=ρLu=Bρ.

Example: Suppose M consists of an uniform conducting material and ρ:MR is a charge density. For the electric field E on M there holds:
divE=ρ,
and for the potential u:MR we have
E=gradu.Taking this together we have to solve:
Δu=ρ,
in order to determine the potential for a given density.
In this setting piecewise constant functions are much more convenient to describe the charge density then piecewise linear ones. Therefore we use ΔPL to solve this problem.

This entry was posted in Lecture. Bookmark the permalink.

Leave a Reply