The completion of locally refined simplicial partitions created by bisection

Abstract

Recently, in [Found. Comput. Math., 7(2) (2007), 245–269], we proved that an adaptive finite element method based on newest vertex bisection in two space dimensions for solving elliptic equations, which is essentially the method from [SINUM, 38 (2000), 466–488] by Morin, Nochetto, and Siebert, converges with the optimal rate.The number of triangles $N$ in the output partition of such a method is generally larger than the number $M$ of triangles that in all intermediate partitions have been marked for bisection, because additional bisections are needed to retain conforming meshes.A key ingredient to our proof was a result from [Numer. Math., 97(2004), 219–268] by Binev, Dahmen and DeVore saying that $N-N_0 \leq C M$ for some absolute constant $C$, where $N_0$ is the number of triangles from the initial partition that have never been bisected. In this paper, we extend this result to bisection algorithms of $n$-simplices, with that generalizing the result concerning optimality of the adaptive finite element method to general space dimensions.

1. Introduction

Nowadays, adaptive finite element methods are a popular tool for the numerical solution of boundary value problems. Compared to non-adaptive finite element methods, they have the potential to achieve the optimal work-accuracy balance allowed by the polynomial degree, under much milder smoothness conditions on the solution of the boundary value problem.

The basic loop of an adaptive finite element method consists of computing the finite element solution with respect to the current partition; computing an a posteriori error estimator, being a sum of local error indicators associated to the individual elements; a marking of those elements for refinement which correspond to the largest error indicators; and finally, the construction of the next partition by refining the marked elements, generally together with elements in some surrounding in order to retain structural properties of the partition needed to apply the error estimator in the next iteration. We refer to this refinement of elements in the surrounding of the marked ones as the completion of the partition.

In this paper, we confine ourselves to partitions into $n$-simplices, as a basic refinement step we use bisection, and as the structural property of the partition we require conformity, meaning that the intersection of any two different simplices in the partition is either empty or a common hyperface of both simplices. In this setting, in order to retain conformity, a bisection of a simplex has to be complemented by bisections of some of its neighbours, which in turn may induce bisections of their neighbours and so on. The complexity of this completion process is being studied in this paper. The advantage of the sketched approach is that highly locally refined partitions can be generated, the arising simplices are uniformly shape regular, and that finite element spaces with respect to refined partitions are nested. Alternatively, one may consider non-conforming partitions generated by other refinement strategies. In that case, a valid error estimator will require that the “amount of non-conformity” is bounded, among other things meaning that the number of hanging vertices per element has to be uniformly bounded. So also then refinements cannot be made on a purely individual element basis, and similar questions arise as with the approach studied here.

In BDD04, considering conforming partitions into triangles generated by the so-called newest vertex bisection rule starting from some fixed initial conforming triangulation, Binev, Dahmen and DeVore showed that the total number of triangles in the partition at termination of the adaptive finite element method is bounded by some absolute multiple of the number of triangles that were marked for refinement in all iterations. In other words, all additional bisections to retain conformity of all intermediate partitions inflate the final number of triangles by not more than a constant factor. In Ste06, we used this result to prove optimal computational complexity of an adaptive linear finite element method, essentially the method introduced in MNS00, in the following sense: Whenever for some $s>0$, the solution can be approximated within a tolerance $\varepsilon >0$ in energy norm by a continuous piecewise linear function with respect to a partition generated by newest vertex bisection with ${\mathcal{O}}(\varepsilon ^{-1/s})$ triangles, and one knows how to approximate the right-hand side in the dual norm with the same rate with piecewise constants; then this adaptive method produces approximations that converge with this rate, using a number of operations that is of the order of the number of triangles in the output partition. This result can be generalized to higher order elements and/or more than two space dimensions, for the latter generalization assuming that the result of Binev, Dahmen and DeVore concerning newest vertex bisection of triangles can be generalized to more space dimensions, which is the topic of this paper.

Bisection of $n$-simplices has been studied in Bän91Kos94AMP00 for $n=3$, and in Mau95Tra97 for general $n$, and this work has been inspired by all of these references. See also Bey00 for refinement strategies not based on bisection. In order to be able to generalize the result from BDD04, it will be important that each uniform refinement of the fixed initial conforming partition is conforming. Here with a uniform refinement, we mean a partition in which all simplices have been created by an equal number of bisections. Conformity of all uniform refinements is not guaranteed with the methods from Bän91AMP00. The other methods require conditions on the initial partition in addition to conformity. In this paper, we apply the bisection rules from Mau95Tra97. We relax the conditions on the initial partition to their minimum. For $n=2$, the resulting conditions can be satisfied for any conforming partition. We show that for $n>2$, any conforming partition of $n$-simplices in any case can be refined to a valid initial partition for our bisection method. For the bisection method being applied inside an adaptive finite element method, we show that the result from BDD04 generalizes to $n$-dimensions: The total number of $n$-simplices in the partition at termination of the method can be bounded by some absolute multiple of the number of $n$-simplices that were marked for refinement in all iterations.

This paper is organized as follows: In §2, we recall results concerning recurrent bisections of a single $n$-simplex. In §3, we show that in order to verify conformity of a partition, we only have to check whether $(n-1)$-dimensional hyperfaces match to $(n-1)$-dimensional hyperfaces, where lower-dimensional hyperfaces can then be ignored. In §4, we formulate minimal conditions on the initial partition under which all uniform refinements are conforming. In Appendix A, we show that these conditions can always be satisfied by some initial refinement of any given conforming subdivision into $n$-simplices. In §5, we demonstrate how local refinements can be made while retaining conformity. Finally, in §6, we prove that the result of Binev, Dahmen and DeVore generalizes to $n$-dimensions.

2. Bisection of a single simplex

Let $2 \leq n \leq m$. An $n$-simplex, or briefly, simplex $T$ in $\mathbf{R}^m$ is the convex hull of $n+1$ points $x_0,\ldots ,x_n \in \mathbf{R}^m$ that do not lie on a $(n-1)$-dimensional hyperplane. We will identify $T$ with the set of its vertices $\{x_0,\ldots ,x_n\}$. For $0 \leq k \leq n-1$, a simplex spanned by $k+1$ vertices of $T$ is called a hyperface of $T$. For $k=n-1$, it will be called a true hyperface, and for $k\leq n-2$ it will called a lower dimensional hyperface.

Corresponding to a simplex $\{x_0,\ldots ,x_n\}$, we will distinguish between $n(n+1)!$ tagged simplices given by all possible ordered sequences $(x_0,x_1,\ldots ,x_n)_{\gamma }$ and types $\gamma \in \{0,\ldots ,n-1\}$. Given a tagged simplex $T=(x_0,x_1,\ldots ,x_n)_{\gamma }$, its children are the tagged simplices

$$\begin{align*} &(x_0,{\textstyle \frac{x_0+x_n}{2}},x_1,\ldots ,x_{\gamma },x_{\gamma +1},\ldots ,x_{n-1})_{(\gamma +1){\mathrm{mod}} n}\\ \end{align*}$$

and

$$\begin{align*} &(x_n,{\textstyle \frac{x_0+x_n}{2}},x_1,\ldots ,x_{\gamma },x_{n-1},\ldots ,x_{\gamma +1})_{(\gamma +1){\mathrm{mod}} n}, \end{align*}$$

where the sequences $(x_{\gamma +1},\ldots ,x_{n-1})$ and $(x_1,\ldots ,x_{\gamma })$ should be read as being void for $\gamma =n-1$ and $\gamma =0$, respectively. So these children are defined by bisecting the edge $\overline{x_0 x_n}$ of $T$, i.e., by connecting its midpoint with the other vertices $x_1,\ldots ,x_{n-1}$, and by an appropriate ordering of their vertices, and by having type $(\gamma +1){\mathrm{mod}} n$. See Figure 1 for an illustration.

Corresponding to a tagged simplex $T=(x_0,\ldots ,x_n)_{\gamma }$, we set

$$T_{\mathrm{R}}=(x_n,x_1,\ldots ,x_{\gamma },x_{n-1},\ldots ,x_{\gamma +1},x_0)_{\gamma },$$

which is the tagged simplex that has the same set of children as $T$, and in this sense is equal to $T$. So actually we distinguish between $\frac{1}{2} n(n+1)!$ tagged simplices.

The edge $\overline{x_0 x_n}$ is called the refinement edge of $T$. In the $n=2$ case, the vertex opposite to this edge is known as the newest vertex, and the procedure is known as newest vertex bisection. A tagged simplex that is created by applying $\ell$ recursive bisections to $T$ is called a level $\ell$ descendant of $T$. One may verify that the refinement edge of a tagged simplex of type 0 will not be further cut until the creation of level $n+1$ descendants. Generally, this is not true for a tagged simplex of type unequal to 0. Yet, an edge will never be cut on two consecutive levels.

The above bisection rule was introduced in Tra97 and, in different notation, in Mau95. The idea behind it is that when starting with a so-called Kuhn simplex, giving it type 0, recurrent bisections always cut the longest edge. A Kuhn simplex is a simplex of the form $\{x_0^{\pi },\ldots ,x_n^{\pi }\}$ with $x^{\pi }_i=\sum _{j=1}^i e_{\pi (j)}$, $\pi$ being a permutation of $\{1,\ldots ,n\}$, and $\{e_1,\ldots ,e_n\}$ the canonical basis for $\mathbf{R}^n$. The set of the $n!$ Kuhn simplices form a partition of the $n$-dimensional hypercube. The following result was proven in Tra97Mau95

Theorem 2.1.

All $2^{\ell }$ level $\ell$-descendants of a tagged Kuhn simplex $(x_0^{\pi },\ldots ,x_n^{\pi })_0$ are mutually congruent. Moreover, the level $n$ descendants are congruent to $(x_0^{\pi },\ldots ,x_n^{\pi })_0$ up to a magnification factor $\frac{1}{2}$. All these congruence mappings between pairs of tagged simplices preserve the ordering of the vertices, showing that all descendants of $(x_0^{\pi },\ldots ,x_n^{\pi })_0$ have at most $n$ different shapes.

Now let $T=(x_0,\ldots ,x_n)_0$ be an arbitrary tagged $n$-simplex of type $0$. Then given arbitrary tagged Kuhn simplices $(x_0^{\pi },\ldots ,x_n^{\pi })_0$ of type $0$, there is a unique affine mapping $F_T:\mathbf{R}^n \rightarrow \mathbf{R}^n$ such that $F(x_i)=x_i^{\pi }$ ($0 \leq i \leq n)$. The definition of the bisection rule shows that the level $\ell$ descendants of $T$ are the images under $F_T^{-1}$ of the level $\ell$ descendants of $(x_0^{\pi },\ldots ,x_n^{\pi })_0$. From Theorem 2.1 we conclude that the smallest angle of any descendant of $T$ stays away from zero only dependent on the smallest angle in $T$. The same is true for $T$ being a tagged simplex of type $\gamma \in \{0,\ldots ,n-1\}$ since its $2^{n-\gamma }$ level $n-\gamma$ descendants are of type $0$.

3. Partitions and conformity

Let $\Omega \subset \mathbf{R}^n$ be an open set. A locally finite collection $P$ of mutually essentially disjoint $n$-simplices in $\mathbf{R}^n$ is called a partition of $\Omega$ when $\overline{\Omega }=\bigcup _{T \in P} T$. Usually a partition $P$ is called conforming when the intersection of any two different $T,T'\in P$ is either empty, or a hyperface of both simplices. In case $\Omega$ lies simultaneously on both sides of an $(n-1)$-dimensional part of its boundary, this condition is unnecessarily restrictive. Instead, we will call $P$ to be conforming when:

$$\begin{align} & \text{For any $T \in P$, $\partial \Omega \cap T$ is the union of hyperfaces of $T$}. {\tag{C1}}\\ & \text{Each $x \in T \cap T'$ ($T$, $T' \in P$) for which for any open ball $B \ni x$, any} {\tag{C2}}\\ & \text{$y \in T \cap B \cap \Omega $, $y' \in T' \cap B \cap \Omega $ are connected by a path through $B \cap \Omega $},\\ & \text{lies on a joint hyperface of $T$ and $T'$}. \end{align}$$

See Figure 2 for an illustration.

Remark 3.1.

When $\Omega$ nowhere lies simultaneously on both sides of an $(n-1)$-dimensional part of its boundary, a path as meant in C2 always exists, so that C2 means that each $x \in T \cap T'$ lies on a joint hyperface of $T$ and $T'$, or, that $T \cap T'$ is the union of joint hyperfaces of $T$ and $T'$. Since furthermore $T \cap T'$ is convex, we conclude that in this case $T\cap T'$, if not empty, is a joint hyperface, i.e., C2 is equivalent to the commonly used definition of conforming.

If, in addition, $\partial \Omega$ is everywhere $(n-1)$-dimensional, i.e., if $\Omega =\operatorname {int}(\overline{\Omega })$, then C2 implies C1. Indeed, let $T \in P$ such that $\partial \Omega \cap T$ is not the union of hyperfaces of $T$. Since $\operatorname {int}(T)\subset \operatorname {int}(\bigcup _{T' \in P} T')=\Omega$, this means that $T$ has a hyperface $F$ that contains in its interior both an $x \in \partial \Omega$ and an $y \in \Omega$. Since $\Omega$ is open, there is an open ball $B \subset \mathbf{R}^n$ such that, with $P_y:=\{T' \in P:T' \ni y\}$, $y \in B \subset \bigcup _{T' \in P_y} T'$. Since the intersection of any two simplices from $P_y$ is a joint hyperface that contains $y$, we have that $F =\bigcap _{T' \in P_y} T'$. As a consequence, there exists an open ball $B' \in \mathbf{R}^n$, such that $x \in B' \subset \bigcup _{T' \in P_y} T'$, and so $x \in \operatorname {int}(\bigcup _{T' \in P_y} T') \subset \Omega$, which gives a contradiction.

The next theorem simplifies the task of verifying whether a partition is conforming. Basically it says that if in a partition true hyperfaces coincide with true hyperfaces, then this automatically holds true for lower dimensional hyperfaces. Different $T,T' \in P$ that share a true hyperface, and for which $T \cap T' \cap \Omega \neq \emptyset$, will be called neighbours.

Theorem 3.2.

A partition $P$ satisfies C2 if and only if any $T, T' \in P$, for which $T \cap T' \cap \Omega$ contains a point interior to a true hyperface of $T$ (or $T'$), are neighbours.

Proof.

Let $P$ satisfy C2 and let $x \in T \cap T' \cap \Omega$. Then for any open ball $B \ni x$, $B \cap T \cap T' \cap \Omega$ is connected, and so $x$ lies on a joint hyperface of $T$ and $T'$. When $x$ is interior to a true hyperface of $T$, we conclude that $T$ and $T'$ are neighbours.

For proving the opposite implication, let $B \ni x$ in the definition of C2 be small enough such that, with $P_x:=\{S \in P:S \ni x\}$, $B \cap T \cap T' \cap \Omega \subset \bigcup _{S \in P_x} S$. Consider a path in $B \cap \Omega$ connecting points $y \in T \cap B \cap \Omega$, $y' \in T' \cap B \cap \Omega$. Since $B \cap \Omega$ is open, such a path can be arranged not to cross lower dimensional hyperfaces of any $S \in P_x$. Let $T=S_0, \ldots , S_p=T'$ be the ordered sequence of simplices in $P_x$ that is passed when traveling along this path connecting $y$ and $y'$. By assumption, and the construction of the path, for any $1 \leq i \leq p$, $S_{i-1}$ and $S_i$ are neighbours. We will now show that for $1\leq q \leq p$, $\bigcap _{i=0}^{q} S_i$ is a hyperface of $S_{q}$. For $q=1$ it is true, and let us assume that it is true for a $q-1 \geq 1$. Then $\bigcap _{i=0}^{q} S_i$, being the intersection of the hyperfaces $\bigcap _{i=0}^{q-1} S_i$ and $S_{q-1} \cap S_q$ of $S_{q-1}$, is a hyperface of $S_{q-1}$ that is contained in $S_{q-1} \cap S_q$, and thus is a hyperface of $S_q$. The point $x$ is contained in $\bigcap _{i=0}^{p} S_i$, which by applying the above result for $q=p$, is a hyperface of $T'$, and similarly of $T$.

■

4. Partitions created by refinements

In the remainder of this paper, we will exclusively consider partitions of tagged simplices that can be created by recurrent bisections, as discussed in §2, starting from some fixed initial partition $P_0$ of tagged simplices of some fixed type $\gamma$. So whenever we refer to a partition $P$, we mean a partition of this kind, and any $T \in P$ is a descendant, with some level $\ell (T)$, of a simplex from $P_0$. A partition $P$ is a uniform refinement of $P_0$ when all its simplices have the same level.

From Theorem 2.1, we infer that all partitions are uniformly shape regular only dependent on $P_0$ and $n$, meaning that the ratio of the radii of the smallest circumscribed and largest inscribed balls of any $T$ is uniformly bounded, only dependent on $P_0$ and $n$. More particular, there exist constants $d,D>0$, only dependent on $P_0$ and $n$, such that for any $T$,

$$\begin{equation} d 2^{-\ell (T)} \leq \mathrm{meas}(T),\quad {\mathrm{diam}}(T) \leq D 2^{-\ell (T)/n}. {\tag{4.1}} \end{equation}$$

In the following we will call two neighbouring tagged simplices $T=(x_0,\ldots ,x_n)_{\gamma }$, $T'=(x'_0,\ldots ,x'_n)_{\gamma '}$ reflected neighbours when the ordered sequence of vertices of either $T$ or $T_{\mathrm{R}}$ coincides with that of $T'$ on all but one position. We will always assume that $P_0$ satisfies the following 2 conditions:

(a)

$P_0$ is conforming.

(b)

Any two neighbouring tagged simplices $T=(x_0,\ldots ,x_n)_{\gamma }$, $T'=(x'_0,\ldots ,x'_n)_{\gamma }$ from $P_0$ match in the sense that if $\overline{x_0 x_n}$ or $\overline{x'_0 x'_n}$ is on $T \cap T'$, then $T$ and $T'$ are reflected neighbours. Otherwise, the pair of neighbouring children of $T$ and $T'$ are reflected neighbours.

Remark 4.1.

If $T$ and $T'$ are reflected neighbours, then the pair(s) of their neighbouring children are reflected neighbours. The opposite statement, however, is not true. E.g., for $n=2$ and arbitrary $\gamma \in \{0,1\}$, neighbours $T=(x_0,x_1,x_2)_{\gamma }$ and $T'=(x'_0,x'_1,x'_2)_{\gamma }$ are reflected neighbours when $\overline{x_0 x_2}=\overline{x'_0 x'_2}$ or $x_1=x'_1$. They are already matching when $\overline{x_0 x_2}=\overline{x'_0 x'_2}$ or $x_1, x'_1 \in T\cap T'$; see Figure 3 for an illustration.

Remark 4.2.

Instead of (b), in Mau95Tra97 it was required that for any neighbouring tagged simplices $T$ and $T'$ the ordered sequence of their vertices coincides on all but one position (being the definition of reflected neighbours in Tra97), which is thus an even stronger condition than being reflected neighbours in our terminology. As shown in Tra97, for a simply connected domain, it can be satisfied if and only if each $(n-2)$-dimensional hyperface not on the boundary of the domain is shared by an even number of simplices. For $n=2$, it means that the valence of any interior vertex should be even. On the other hand, for $n=2$ condition (b) corresponds to the condition described in BDD04, Lemma 2.1. There it is shown that for any conforming partition into triangles there exists a local numbering of the vertices that satisfies (b).

We do not know whether for $n>2$, condition (b) can be satisfied for each conforming partition. Therefore, inspired by such a construction for $n=3$ in Kos94, in Appendix A we show that any conforming partition of $n$-simplices can be refined to a conforming partition $P_0$ of tagged simplices of type $n-1$ such that any two neighbours are reflected neighbours, which is thus stronger than needed for (b).

We now proceed assuming $P_0$ satisfies (a) and (b).

Theorem 4.3.

Any uniform refinement $P$ of $P_0$ is conforming.

Proof.

Since $P$ is a refinement of $P_0$, it satisfies C1. Thanks to Theorem 3.2, it only remains to show that any $T, T'\in P$, for which $T \cap T' \cap \Omega$ contains a point interior to a true hyperface of $T$ (or $T'$), are neighbours. If $T$ and $T'$ have the same ancestor in $P_0$, then this has been shown in Tra97, §5. Otherwise, with different ancestors $S=(x_0,\ldots ,x_n)_{\gamma }$ and $S'=(x'_0,\ldots ,x'_n)_{\gamma }$ from $P_0$ of $T$ and $T'$, respectively, $S \cap S' \cap \Omega$ contains a point interior to a true hyperface of $S$ (or $S'$), and so $S$ and $S'$ are neighbours by (a).

If $\overline{x_0 x_n}$ or $\overline{x'_0 x'_n}$ is on $S \cap S'$, then $S$ and $S'$ are reflected neighbours by (b), and so on any level $\ell$ the subdivision of $S$ into $2^{\ell }$ descendants is a reflection in $S \cap S'$ of the corresponding subdivision of $S'$. This is easily seen when the ordered sequences of vertices of $S$ and $S'$ coincide on all but one positions, but the same is true when the ordered sequences of vertices of $S_{\mathrm{R}}$ and $S'$ coincide on all but one positions, since $S_{\mathrm{R}}$ and $S$ have the same children. We conclude that in this case $T$ and $T'$ are neighbours.

Otherwise, (b) shows that the children of $S$ and $S'$ that have $S\cap S'$ as a hyperface, and thus which contain $T$ and $T'$, respectively, are reflected neighbours. The same argument shows that $T$ and $T'$ are neighbours also in this case.

■

Remark 4.4.

Giving our bisection rule, (b) and obviously (a) are actually also necessary conditions for conformity of all uniform refinements of $P_0$. Indeed, since an edge is never cut on two consecutive levels, if $T$ and $T'$ as in (b) both have their refinement edge not on $T \cap T'$, then the pair of their neighbouring children have their refinement edges on their common true hyperface. So, to show the necessity of (b), it is sufficient to show that, for any $\gamma$, if any of two neighbours $T=(x_0,\ldots ,x_n)_{\gamma }$, $T'=(x'_0,\ldots ,x'_n)_{\gamma }$ have their refinement edge on $T \cap T'$, then the union of their level $\ell$ descendants can only form conforming partitions for any $\ell$ when $T$ and $T'$ are reflected neighbours. Suppose they are not, meaning that the ordered sequences of vertices of both $T$, $T'$ and $T_{\mathrm{R}}$, $T'$ differ on more than one position. It is needed that $\overline{x_0 x_n}=\overline{x'_0 x '_n}$, since otherwise already their level 1 descendants do not form a conforming partition. By possibly replacing $T$ by $T_{\mathrm{R}}$, we may assume that $x_0=x'_0$ and $x_n=x'_n$. By the assumption that the ordered sequences of vertices differ on more than one position, and the fact that $T$ and $T'$ are neighbours, there exists an $i \in \{1,\ldots ,n-1\}$ with $x_i \neq x'_i$ and $x_i$ or $x'_i$ on $T \cap T'$. For each $\ell$, there exists one level $\ell$ descendant $T_{\ell }$ ($T'_{\ell }$) of $T$ ($T'$) having vertex $x_0$ ($x'_0$) and a true hyperface on $T \cap T'$. So as long as for increasing $\ell$, the union of the level $\ell$ descendants of $T$ and $T'$ form a conforming partition, $T_{\ell }$ and $T'_{\ell }$ are neighbours. At some level $\ell$, however, depending on $i$ and $\gamma$, $T_{\ell }$ will be cut along $\overline{x_0 x_i}$ and $T'_{\ell }$ along $\overline{x'_0 x'_i}$, meaning that on level $\ell +1$ the partitions are nonconforming, completing the proof of the necessity of (b).

Remark 4.5.

In Bän91AMP00, algorithms for bisection tetrahedra, i.e., for $n=3$, are formulated that do not require a matching of neighbours in the initial partition. With these methods, however, Theorem 4.3 is generally not valid; only uniform refinements with levels divisible by $n$ are guaranteed to be conforming. The result of Theorem 4.3, however, will be heavily used in the following. An interesting open question is whether the tetrahedra on level $n$ generated by the algorithms from Bän91AMP00 can be retagged so that (b) is satisfied. In contrast to the construction from Appendix A, this would give an initial refinement based on bisections. For $n=2$, starting with an arbitrary tagging of the triangles, the triangles on level 2 can always be locally retagged such that (b) is valid (see BDD04, p. 229), whereas a suitable tagging of the initial partition might not be easy to find.

In the following, tagged neighbours will be called compatibly divisible when they have the same refinement edge. For a partition $P$, and $T \in P$, we set

$$N(P,T):= \{\, \text{neighbours $T'$ of $T$ in $P$ that contain the refinement edge of $T$}\,\}.$$

Corollary 4.6.

For any partition $P$, $T\in P$, and $T' \in N(P,T)$, either

•

$\ell (T')=\ell (T)$ and $T,T'$ are compatibly divisible, or

•

$\ell (T')=\ell (T)-1$ and $T$ is compatibly divisible with one of the children of $T'$.

Proof.

For some $p \geq 2$, let $T_1,T_2$ be neighbours with $\ell (T_1) = \ell (T_2) -p$. Then there is a level $p$ descendant of $T_1$ that contains a point of $T_2 \cap \Omega$ interior to a true hyperface. Theorem 4.3 shows that this level $p$ descendant is a neighbour of $T_2$, i.e., that it has a true hyperface in common with $T_2$ and thus with $T_1$. Since a level $p \geq 2$ descendant of $T_1$ has less than $n-1$ vertices in common with $T_1$, we arrive at a contradiction, and conclude that the levels of neighbours differ at most one.

Now let $T' \in N(P,T)$ with $\ell (T')=\ell (T)+1$. Then again Theorem 4.3 shows that one of both children of $T$ is a neighbour of $T'$. However, since $T$ has its refinement edge on $T \cap T'$ this cannot be the case.

Concerning the two remaining cases, if $\ell (T')=\ell (T)$, then $T,T'$ are indeed compatibly divisible, since otherwise the uniform refinement with simplices of level $\ell (T)+1$ would not be conforming.

If $\ell (T')=\ell (T)-1$, then one of both children of $T'$ has a point of $T \cap \Omega$ interior to a true hyperface, so that they are neighbours by Theorem 4.3. Since the uniform refinement with simplices of level $\ell (T)+1$ is conforming, we conclude that this child and $T$ are compatibly divisible.

■

5. Local refinements while retaining conformity

Let $P$ be a conforming partition, and let $M \subset P$ be a subset of simplices that have been marked for bisection. After bisecting the simplices from $M$, a generally nonconforming partition $P'$ arises. To restore conformity, one may apply the following completion algorithm:

Since the only way to cure the situation as described in the for-statement, or towards curing it, is to bisect $T$, complete$[P']$ outputs the smallest conforming refinement of $P'$, assuming that a conforming refinement exists. This, however, holds true, since with $\ell =\max _{T' \in P'} \ell (T')$, the uniform partition with simplices of level $\ell$ is a conforming refinement of $P'$. When implementing complete, care has to be taken to ensure that the computational work is of the order of the number of bisections that are made.

An alternative for first bisecting all simplices in $M$ and then restoring conformity by a call of complete, is, when running over $T \in M$, for each of those $T$ to replace the current partition $P$ by its smallest conforming refinement in which $T$ has been bisected. A call of the routine refine$[P,T]$ given below determines such a partition. Since it bisects generally more simplices than only $T$, it may happen that it bisects $T' \in M$ for which a call has not yet been made, which call thus can be skipped. In other words, the number of calls of refine is never larger, but might be smaller than the number of marked simplices. Since also with this approach, only simplices are bisected that either are marked, or whose bisection is unavoidable for obtaining a conforming partition, again we end up with the smallest conforming partition in which all marked simplices are bisected.

The routine refine$[P,T]$ is a generalization to $n$-dimensions of such a routine by Kossaczký in Kos94 for bisecting tetrahedra. Based on Corollary 4.6, the idea is to determine, possibly by recursive calls, a closed set of compatibly divisible neighbours that share the refinement edge with $T$, after which this set of simplices can be simultaneously bisected without introducing nonconformities.

Theorem 5.1.

$P':={\mathbf{refine}}[P,T]$ terminates, and $P'$ is the smallest conforming refinement of $P$ in which $T$ has been bisected. If $T' \in P'$ is newly created by the call, then $\ell (T') \leq \ell (T)+1$.

Proof.

Let $\ell (T)=0$. Then Corollary 4.6 shows that there will be no recursive calls of refine, and that just before any evaluation of the until-statement, all $T' \in K$ have the same refinement edge as $T$, and satisfy $\ell (T')=\ell (T)$ and $N(P,T') \subset K \cup F$. If $F \neq \emptyset$, then in the next iteration of the do-until loop, the set $K$ will be extended. Since, on the other hand, from the uniform shape regularity we know that the cardinality of $K$ is bounded, we conclude that this loop terminates. After termination, $F=\emptyset$, and so for all $T' \in K$, $N(P,T') \subset K$, by Theorem 3.2 meaning that by bisecting all $T' \in K$ conformity is retained. It is clear that we cannot confine bisection to a smaller set of simplices, and that $\ell (T') = \ell (T)+1$ for any newly created $T'$.

Assuming that for some $\ell -1 \geq 1$, the statement is true for $T$ with $\ell (T) = \ell -1$, let us consider $T$ with $\ell (T)=\ell$. Possible recursive calls of ${\mathbf{refine}}[P,T'']$ are unavoidable, where Corollary 4.6 shows that $\ell (T'')=\ell (T)-1$. The induction hypothesis then shows that such a call outputs the smallest conforming partition in which $T''$ has been bisected, and moreover, that it does not bisect any simplex that is already in $K \cup F$, since that would create simplices with levels larger than $\ell (T)=\ell (T'')+1$. Now the proof is completed using the same arguments as in the $\ell (T)=0$ case.

■

Assuming that the data structures allow that the determination of $N(P,T)$ requires not more than an absolute constant number of operations, note that the number of operations needed for $P':={\mathbf{refine}}[P,T]$ is ${\mathcal{O}}(\#P'-\#P)$.

In addition to the properties of refine shown in Theorem 5.2, we have

Theorem 5.2.

With the constant $D$ from 4.1, any newly created $T'$ by the call ${\mathbf{refine}}[P,T]$ satisfies

$$d(T',T):=\inf _{x' \in T',\, x \in T} |x'-x| \leq D 2^{1/n} \sum _{k =\ell (T')}^{\ell (T)} 2^{-k/n} \quad \left(< \frac{D 2^{1/n}}{1-2^{-1/n}} 2^{-\ell (T')} \right).$$

Proof.

For $\ell (T)=0$, any newly created $T'$ is a child of a $\tilde{T}$ that has its refinement edge on $\partial T$, so that $d(T',T)=0$. Note that in this case the sum over $k$ is empty since $\ell (T') =\ell (T)+1$.

Assuming that the theorem holds for $\ell (T)=\ell -1\geq 0$, let us consider $T$ with $\ell (T)=\ell$. If $T'$ is created by bisection of any simplex from the set $K$, then the statement is proven as in the $\ell (T)=0$ case. If $T'$ is created by a recursive call ${\mathbf{refine}}[P,T'']$, then using $T \cap T'' \neq \emptyset$, the induction hypothesis shows that

$$\begin{align*} d(T',T) & \leq d(T',T'')+ {\mathrm{diam}}(T'') \\ &\leq D 2^{1/n} \sum _{k =\ell (T')}^{\ell (T'')} 2^{-k/n} + D 2^{-\ell (T'')/n} = D 2^{1/n} \sum _{k =\ell (T')}^{\ell (T)} 2^{-k/n}, \end{align*}$$

by $\ell (T'')=\ell (T)-1$.

■

The routine refine provides an alternative for the straightforward bisection of marked simplices complemented with a call of complete. Here, it is mainly discussed because, in the next section, its properties proven in Theorems 5.1 and 5.2 will allow us to bound the complexity of a recurrent marking and completion process. It turns out, however, that an implementation of this process by means of calls of refine is particularly efficient. For this reason, this approach is followed in the adaptive finite element package ALBERTA (SS05).

Remark 5.3.

Inside adaptive finite element methods, simplices can be marked for multiple bisections. This means that not only these simplices should be bisected, but also some of their descendants, with the obvious restriction that a descendant can only be on the list for bisection when its parent is. For example, for $n=2$, the adaptive finite element method introduced in MNS00 selects triangles for their bisection, and that of their children and 2 of their 4 grandchildren. The evaluation of such multiple markings can be done by scheduling them as an ordered sequence of groups of single markings, where the marking of a child is in the next group as that of its parent. After finding the smallest conforming refinement in which all simplices from a group are bisected, it may happen that bisections corresponding to markings from the next groups have already taken place, so that these markings can be deleted.

6. The complexity of a recurrent marking and completion process

We study the following algorithm:

As we have seen, the output partition of this algorithm is the smallest conforming refinement of $P_0$ in which all marked simplices have been bisected. After the preparations from the previous sections, the proof of the following main theorem concerning this algorithm follows the lines of the proof of the corresponding theorem for $n=2$ by Binev, Dahmen and DeVore. Since there are some small modifications, we include the proof for the reader’s convenience.

Theorem 6.1 (generalizes BDD04, Theorem 2.4 for $n=2$).

With $M$ being the set of simplices for which a call of refine is made in the above algorithm, which set is thus not larger than the union of all marked simplices, for the output partition $P$ it holds that $\# ( P \backslash (P \cap P_0)) \lesssim \# M$, only dependent on the constants $d,D$ from 4.1, and $n$.

Proof.

Fixing $n$, let $a:\mathbf{N}_0 \cup \{-1\} \rightarrow \mathbf{R}^{+}$, $b:\mathbf{N}_0 \rightarrow \mathbf{N}$ be some sequences with $\sum _{p=-1}^{\infty } a(p)<\infty$, $\sum _{p=0}^{\infty } b(p) 2^{-p/n} <\infty$, and $\inf _{p \geq 0} b(p) a(p) >0$. Valid instances are $a(p)=(p+2)^{-2}$ and $b(p)=2^{p/(n+1)}$. Let $A:=D (\frac{2^{1/n}}{1-2^{-1/n}}+1) \sum _{p=0}^{\infty } b(p) 2^{-p/n}$.

Inside this proof, $P$ will always denote the output partition of the algorithm, whereas any intermediate partition will be denoted as $\bar{P}$. We define $\lambda : P \times M$ by

$$\lambda (T',T)=\left\{\begin{array}{cl} a(\ell (T)-\ell (T')) & \text{if } d(T',T) < A 2^{-\ell (T')/n} \text{ and }\ell (T') \leq \ell (T)+1,\\0 & \text{otherwise.} \end{array} \right.$$

For any fixed $T \in P$, and $\ell ' \in \mathbf{N}_0$ with $\ell '\leq \ell (T)+1$, there exists a uniformly bounded number, only dependent on $d$ and $D$, of $T'\in P$ with $d(T',T) < A 2^{-\ell (T')/n}$ and $\ell (T')=\ell '$. In view of the definition of $\lambda$, we thus have $\sum _{T' \in P} \lambda (T',T) \lesssim \sum _{p=-1}^{\infty } a(p) <\infty$, and so $\sum _{T \in M}\sum _{T' \in P} \lambda (T',T) \lesssim \#M$.

In the second part of this proof, we are going to show that for all $T' \in P \backslash (P \cap P_0)$,

$$\begin{equation} \sum _{T \in M} \lambda (T',T) \gtrsim 1, {\tag{6.1}} \end{equation}$$

only dependent on $d$, $D$ and $n$, so that

$$\# (P \backslash (P \cap P_0) \lesssim \sum _{T' \in P \backslash (P \cap P_0)}\sum _{T \in M} \lambda (T',T) \leq \sum _{T \in M} \sum _{T' \in P }\lambda (T',T) \lesssim \#M,$$

as required.

Let $T_0 \in P\backslash (P \cap P_0)$. For $j \geq 0$, given that $T_j$ has been defined and assuming that it is not in $P_0$, we let $T_{j+1} \in M$ be such that $T_j$ has been created by the call ${\mathbf{refine}}[\bar{P},T_{j+1}]$. Let $s$ be the smallest integer such that $\ell (T_s)=\ell (T_0)-1$. Note that such an $s$ exists since at some point the sequence ends with a $T_{\tilde{\jmath }} \in P_0$, thus with $\ell (T_{\tilde{\jmath }})=0$, whereas the value $\ell (T_0)-1$ cannot be passed without being attained because $\ell (T_{j+1}) \geq \ell (T_j)-1$ by Theorem 5.1. From Theorem 5.2 and 4.1, for $1 \leq j \leq s$ we have

$$\begin{align*} d(T_0,T_j) & \leq d(T_0,T_1)+\mathrm{diam}(T_1)+d(T_1,T_j) \\ & \leq \sum _{k=1}^j d(T_{k-1},T_k) +\sum _{k=1}^{j-1} \mathrm{diam}(T_k) \\ & < \sum _{k=1}^j \frac{D 2^{1/n}}{1-2^{-1/n}} 2^{-\ell (T_{k-1})/n}+\sum _{k=1}^{j-1} D 2^{-\ell (T_k)/n}\\ & < D(1+\frac{2^{1/n}}{1-2^{-1/n}}) \sum _{k=0}^{j-1} 2^{-\ell (T_k)/n} \\ & = D(1+\frac{2^{1/n}}{1-2^{-1/n}}) \sum _{p=0}^{\infty } m(p,j) 2^{-(\ell (T_0)+p)/n}, \end{align*}$$

where $m(p,j)$ denotes the number of $k \leq j-1$ with $\ell (T_k)=\ell (T_0)+p$.

In case $m(p,s) \leq b(p)$ for all $p$, then the definition of the constant $A$ shows that $d(T_0,T_s) < A 2^{-\ell (T_0)/n}$, and so by definition of $\lambda$, we conclude that $\lambda (T_0,T_s)=a(\ell (T_s)-\ell (T_0))=a(-1)$, which shows 6.1.

Otherwise, there exist $p$ with $m(p,s) > b(p)$. For each of those $p$, there exists a smallest $j=j(p)$ with $m(p,j(p)) > b(p)$. We denote $p$ that gives rise to the smallest $j(p)$ as $p^*$, and denote $j(p^*)$ as $j^*$. Thus $m(p,j^*-1) \leq b(p)$ for all $p$, and $m(p^*,j^*-1)=b(p^*)$. As in the case that $m(p,s) \leq b(p)$ for all $p$, we find that for all $k \leq j^*-1$, $d(T_0,T_k) < A 2^{-\ell (T_0)/n}$ and $\lambda (T_0,T_k)=a(\ell (T_k)-\ell (T_0))$. In view of the definition of $m(\cdot ,\cdot )$, we find that

$$\begin{align*} \sum _{\{k \leq j^*-2: \ell (T_k)=\ell (T_0)+p^*\}} \lambda (T_0,T_k) &= m(p^*,j^*-1)a(p^*)\\ &= b(p^*)a(p^*) \geq \inf _{p \geq 0} b(p)a(p) >0, \end{align*}$$

showing 6.1 also in this case.

■

The only properties that have been used in this proof are 4.1, and that of refine given in Theorems 5.1 and 5.2.

Figure 1.

Bisection of a tagged tetrahedron of type $0$ with the next two level cuts indicated

Figure 2.

Tetrahedra in a conforming (left) or nonconforming (right) partition of $\mathbf{R}^3 \backslash [0,1]^2\times \{0\}$. Dashed edges are in $\mathbf{R}^2 \times \{0\}$

Figure 3.

Matching neighbours for $n=2$, and their level 1 and 2 descendants. The neighbours in the rightmost picture are not reflected neighbours, but the pair of their neighbouring children are.

Figure 4.

Subdivision of a tetrahedron into $4 \times 3$ tetrahedra with the labeling of vertices and marking of edges

Figure 5.

Local numbering of the vertices of the subtriangles of a macro-triangle