We want to derive a discrete version of the laplace operator defined on triangulated surfaces. At first we will define what a triangulated surface with and without boundary is, and consider triangulated domains of $\mathbb{R}^2$ as an important example.
Let $\Sigma$ be a two dimensional simplicial complex and let $V$ denote its set of vertices. For $i \in V$ the “vertex-star” around $i$ is defined as:
\[S_i := \left\{ j \in V\, \big \vert \, j \neq i, \, \{i,j\} \in \Sigma \right\}.\]The link of a vertex $i \in V$ is a graph $G_i$ given by:
\[G_i := \left\{ \{j,k\}\subset S_i \,\big \vert \, j \neq k, \, \{i,j,k\} \in \Sigma\right\}.\]
Definition: A triangulated surface with boundary is a two dimensional simplicial complex $\Sigma$ with the following properties:
1) Each edge is contained in exactly one or two triangles.
2) For each vertex $i \in V$ the corresponding link $G_i$ is connected.
A vertex of a link $G_i$ has either one or two edges. In a triangulated surface with boundary all links $G_i$ are connected thus they are either a discrete interval or a discrete circle. In the first case the corresponding vertex $i$ is called a boundary vertex in the second case it is called an interior vertex. Also the edges of an triangulated surface split in two groups. The one that are contained in only one triangle are the boundary edges, the one that lie in two triangles are interior edges. The set of all boundary vertices and edges of an triangulated surface with boundary is a graph, called the boundary of $\Sigma$ and will be denoted with $\partial \Sigma$.
The boundary is either empty or the union of discrete circles. If the boundary is empty $\Sigma $ is called a triangulated surface.
Definition: A triangulated domain $M$ in $\mathbb{R}^2$ is a triangulated surface with boundary $\Sigma$ together with an assignment $p:V\rightarrow \mathbb{R}^2$ such that its piecewise linear extension $\tilde{p}: C(\Sigma) \rightarrow \mathbb{R}^2$ is injective. Then $M$ is given by the following disjoint union:
\[M= \bigcup_{S \in \Sigma}^{\circ} \tilde{p} \left(\overset{\circ}{C(S)}\right).\]
Here $\tilde{p} \left(\overset{\circ}{C(S)}\right)$ denotes the interior of the affine realization of the simplex $S$. For a triangle this is the triangle minus its edges, for an edge it is the edge minus its vertices and the interior of a point is just the point it self.
For $\sigma \in \Sigma_2 $ let $T_{\sigma}:=\tilde{p}\left(C(\sigma)\right)$ denote the corresponding triangle in $M \subset \mathbb{R}^2$ and for $i \in V$, $p_i:=\tilde{p}\left(\delta(i) \right)$ the corresponding point .
On a triangulated domain $M \subset \mathbb{R}^2$ we consider the following set of functions:
\[W:=\left\{ f:M\rightarrow \mathbb{R} \, \big \vert \,\left. f\right|_{T_{\sigma}} \mbox{ is affine for all } \sigma \in \Sigma_2, \, \left. f\right|_{\partial M}=0 \right\}\]
We can equip $W$ with the usual scalar-product:
\begin{align*}\langle\!\langle\cdot, \cdot \rangle\!\rangle &: W\times W \rightarrow \mathbb{R}, \\ \langle\!\langle f, g \rangle\!\rangle & := \int_M fg.\end{align*}
On the interior of each triangle $T_{\sigma}$, $f \in W$ is a differentiable function with constant derivative. Therefore, for all $\sigma \in \Sigma_2$ there exist $X_{\sigma} \in \mathbb{R}^2$ such that $\mbox{grad}\,f(p) = X_{\sigma}$ for all $p \in \overset{\circ}{T_{\sigma}}$. More general we define the set of vector fields on $M$:
\[VF(M):= \left\{X:\bigcup_{\overset{\circ}{T_{\sigma}},\,\sigma \in \Sigma_2}\rightarrow \mathbb{R}^2 \,\bigg \vert \,\left. X\right|_{\overset{\circ}{T_{\sigma}}} = X_{\sigma}=\mbox{constant, for all } \sigma\in \Sigma_2\right\}\]
Also on $VF(M)$ we can define a scalar product:
\begin{align*}\langle\!\langle\cdot, \cdot \rangle\!\rangle &: VF(M)\times VF(M) \rightarrow \mathbb{R}, \\ \langle\!\langle X, Y \rangle\!\rangle & := \sum_{ \sigma\in \Sigma_2}\langle X_{ \sigma},Y_{ \sigma}\rangle A_{ \sigma},\end{align*}
where $A_{ \sigma}$ denotes the area of $T_{\sigma}.$
Let $\overset{\circ}{V}$ denote the set of interior vertices of $\Sigma$ and $N:=\left|\overset{\circ}{V}\right|$ the number of interior vertices. A function $f \in W$ is completely determined by its values $f_i:= f(p_i)$ at the interior vertices of the triangulation. In deed, $W$ is a $N$ dimensional vectorspace with basis $\left\{\phi_i\right\}$, where $\phi_i \in W$ is defined by $\phi_i(p_j):=\delta_{ij}.$ The $\phi_i$ are often called “hat-function” and there holds:
\[f = \sum_{i \in \overset{\circ}{V}} f_i \phi_i.\]
Thus in order to compute the scalar product of arbitrary functions $f,g \in W$ we just need to know the values:
\[b_{ij}:=\langle\!\langle\phi_i, \phi_j \rangle\!\rangle.\]
For $\{i,j\}\notin \Sigma$ we have $b_{ij}:=\langle\!\langle\phi_i, \phi_j \rangle\!\rangle=0.$
In order to compute the non zero elements consider the domain \[D:= \left\{(s,t) \in \mathbb{R}^2 \, \big \vert \, 0\leq s,t,s+t \leq 1\right\},\]
and for each triangle $T_{\sigma}$ with vertices $p_i,p_j,p_k$ and edges $e_{k}:= p_j – p_i$, $e_{i}:= p_k – p_j$, $e_{j}:= p_i – p_k$ the following parametrization:
\begin{align*}\Phi &:D \rightarrow T_{\sigma} \subset \mathbb{R}^2, \\ \Phi(s,t) &:= p_i + t e_{k} – s e_{j}.\end{align*}
$\Phi$ is bijective and we have:
\[\mbox{det}\left( \Phi’\right) = \mbox{det}\left( e_{k},-e_{j}\right) = 2A_{\sigma}.\]
Now we can compute $\langle\!\langle\phi_i, \phi_i \rangle\!\rangle$:
\begin{align*}\int_{T_{\sigma}} \phi_i^2 & = \int_D \left(\phi_i \circ \Phi\right)^2 \left| \,\mbox{det}\left( \Phi’\right)\right| \\ &= \int_D (1-s-t)^2 2A_{\sigma} \,ds dt \\ &= 2A_{\sigma} \int_0^1\int_0^{1-t} (1-s-t)^2 ds dt \\ &= 2A_{\sigma} \int_0^1 \frac{-1}{3} \left. (1-s-t)^3\right|_0^{1-t} dt \\ &= 2A_{\sigma} \int_0^1 \frac{1}{3} (1-t)^3 dt\\ & = \frac{A_{\sigma}}{6}.
\end{align*}
Summation over all triangles that contain the vertex $i$ gives us the result:
\[b_{ii} = \langle\!\langle\phi_i, \phi_i \rangle\!\rangle = \int_M \phi_i^2 =\sum_{\sigma \,\vert \, i \in\sigma }\int_{T_{\sigma}} \phi_i^2 = \frac{1}{6} \sum_{\sigma \,\vert \, i \in\sigma }A_{\sigma}.\]
To every vertex $i \in V$ we can assign an area
\[A_i:=\frac{1}{3} \sum_{\sigma \,\vert \, i \in\sigma }A_{\sigma},\] and obtain $\langle\!\langle\phi_i, \phi_i \rangle\!\rangle = \frac{1}{2} A_i.$ Using $\left(\phi_j \circ \Phi\right)(s,t) = s$ and $\left(\phi_k \circ \Phi\right)(s,t) = t$ we obtain the analog result for $\langle\!\langle\phi_j, \phi_k \rangle\!\rangle$:
\begin{align*}\int_{T_{\sigma}} \phi_j \phi_k & = \int_D \left(\phi_j \circ \Phi\right) \left(\phi_k \circ \Phi\right) \left| \,\mbox{det}\left( \Phi’\right)\right| \\ & = 2A_{\sigma}\int_D st \, ds dt \\ &= 2A_{\sigma} \int_0^1\int_0^{1-t} st \, ds dt \\ & = A_{\sigma} \int_0^1 \left. ts^2\right|_0^{1-t} dt \\ &= A_{\sigma} \int_0^1 t^3-2t^2+t \, dt \\ &= \frac{A_{\sigma}}{12}.
\end{align*}
And again we get the result by summation over the two triangles that contain $j$ and $k$:
\[b_{jk} = \langle\!\langle\phi_j, \phi_k \rangle\!\rangle = \frac{1}{12} \sum_{\sigma \,\vert \, k,j \in\sigma }A_{\sigma}.\]
The scalar product of two functions $f = \sum_{i \in \overset{\circ}{V}} f_i \phi_i, \quad g = \sum_{i \in \overset{\circ}{V}} g_i \phi_i$ can now be computed in the following way:
\[\langle\!\langle f, g \rangle\!\rangle = \sum_{i,j \in \overset{\circ}{V}} f_i g_j \langle\!\langle\phi_i, \phi_j \rangle\!\rangle = \sum_{i,j \in \overset{\circ}{V}} f_i g_j b_{ij}.\]