# 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 in the output partition of such a method is generally larger than the number 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 for some absolute constant where , 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 with that generalizing the result concerning optimality of the adaptive finite element method to general space dimensions. -simplices,

## 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 as a basic refinement step we use bisection, and as the structural property of the partition we require -simplices,*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 ReferenceBDD04, 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 ReferenceSte06, we used this result to prove optimal computational complexity of an adaptive linear finite element method, essentially the method introduced in ReferenceMNS00, in the following sense: Whenever for some the solution can be approximated within a tolerance , in energy norm by a continuous piecewise linear function with respect to a partition generated by newest vertex bisection with 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 has been studied in -simplicesReferenceBän91ReferenceKos94ReferenceAMP00 for and in ,ReferenceMau95ReferenceTra97 for general and this work has been inspired by all of these references. See also ,ReferenceBey00 for refinement strategies not based on bisection. In order to be able to generalize the result from ReferenceBDD04, 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 ReferenceBän91ReferenceAMP00. The other methods require conditions on the initial partition in addition to conformity. In this paper, we apply the bisection rules from ReferenceMau95ReferenceTra97. We relax the conditions on the initial partition to their minimum. For the resulting conditions can be satisfied for any conforming partition. We show that for , any conforming partition of , 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 -simplicesReferenceBDD04 generalizes to The total number of -dimensions: in the partition at termination of the method can be bounded by some absolute multiple of the number of -simplices that were marked for refinement in all iterations. -simplices

This paper is organized as follows: In §2, we recall results concerning recurrent bisections of a single In § -simplex.3, we show that in order to verify conformity of a partition, we only have to check whether hyperfaces match to -dimensional hyperfaces, where lower-dimensional hyperfaces can then be ignored. In § -dimensional4, 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 In § -simplices.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 -dimensions.

## 2. Bisection of a single simplex

Let An . or briefly, simplex -simplex, in is the convex hull of points that do not lie on a hyperplane. We will identify -dimensional with the set of its vertices For . a simplex spanned by , vertices of is called a hyperface of For . it will be called a ,*true hyperface*, and for it will called a *lower dimensional hyperface*.

Corresponding to a simplex we will distinguish between , *tagged* simplices given by all possible *ordered* sequences and *types* Given a tagged simplex . its children are the tagged simplices ,

and

where the sequences and should be read as being void for and respectively. So these children are defined by bisecting the edge , of i.e., by connecting its midpoint with the other vertices , and by an appropriate ordering of their vertices, and by having type , See Figure .1 for an illustration.

Corresponding to a tagged simplex we set ,

which is the tagged simplex that has the same set of children as and in this sense is equal to , So actually we distinguish between . tagged simplices.

The edge is called the *refinement edge* of In the . 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 recursive bisections to is called a level descendant of One may verify that the refinement edge of a tagged simplex of type 0 will not be further cut until the creation of level . 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 ReferenceTra97 and, in different notation, in ReferenceMau95. 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 with , being a permutation of and , the canonical basis for The set of the . Kuhn simplices form a partition of the hypercube. The following result was proven in -dimensionalReferenceTra97ReferenceMau95

### Theorem 2.1

All level of a tagged Kuhn simplex -descendants are mutually congruent. Moreover, the level descendants are congruent to up to a magnification factor All these congruence mappings between pairs of tagged simplices preserve the ordering of the vertices, showing that all descendants of . have at most different shapes.

Now let be an arbitrary tagged of type -simplex Then given arbitrary tagged Kuhn simplices . of type there is a unique affine mapping , such that ( The definition of the bisection rule shows that the level . descendants of are the images under of the level descendants of From Theorem .2.1 we conclude that the smallest angle of any descendant of stays away from zero only dependent on the smallest angle in The same is true for . being a tagged simplex of type since its level descendants are of type .

## 3. Partitions and conformity

Let be an open set. A locally finite collection of mutually essentially disjoint in -simplices is called a *partition* of when Usually a partition . is called conforming when the intersection of any two different is either empty, or a hyperface of both simplices. In case lies simultaneously on both sides of an part of its boundary, this condition is unnecessarily restrictive. Instead, we will call -dimensional to be *conforming* when:

See Figure 2 for an illustration.

### Remark 3.1

When nowhere lies simultaneously on both sides of an part of its boundary, a path as meant in -dimensionalEquationC2 always exists, so that EquationC2 means that each lies on a joint hyperface of and or, that , is the union of joint hyperfaces of and Since furthermore . is convex, we conclude that in this case if not empty, ,*is* a joint hyperface, i.e., EquationC2 is equivalent to the commonly used definition of conforming.

If, in addition, is everywhere i.e., if -dimensional, then ,EquationC2 implies EquationC1. Indeed, let such that is not the union of hyperfaces of Since . this means that , has a hyperface that contains in its interior both an and an Since . is open, there is an open ball such that, with , Since the intersection of any two simplices from . is a joint hyperface that contains we have that , As a consequence, there exists an open ball . such that , and so , 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 that share a true hyperface, and for which will be called ,*neighbours*.

### Theorem 3.2

A partition satisfies EquationC2 if and only if any for which , contains a point interior to a true hyperface of (or are neighbours. ),

### Proof.

Let satisfy EquationC2 and let Then for any open ball . , is connected, and so lies on a joint hyperface of and When . is interior to a true hyperface of we conclude that , and are neighbours.

For proving the opposite implication, let in the definition of EquationC2 be small enough such that, with , Consider a path in . connecting points , Since . is open, such a path can be arranged not to cross lower dimensional hyperfaces of any Let . be the ordered sequence of simplices in that is passed when traveling along this path connecting and By assumption, and the construction of the path, for any . , and are neighbours. We will now show that for , is a hyperface of For . it is true, and let us assume that it is true for a Then . being the intersection of the hyperfaces , and of is a hyperface of , that is contained in and thus is a hyperface of , The point . is contained in which by applying the above result for , is a hyperface of , and similarly of , .

■## 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 of tagged simplices of some fixed type *. So whenever we refer to a partition we mean a partition of this kind, and any , is a descendant, with some level of a simplex from , A partition . is a *uniform refinement* of when all its simplices have the same level.

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

In the following we will call two neighbouring tagged simplices , *reflected neighbours* when the ordered sequence of vertices of either or coincides with that of on all but one position. We will *always assume that satisfies the following 2 conditions:*

- (a)
is conforming.

- (b)
Any two neighbouring tagged simplices , from

*match*in the sense that if or is on then , and are reflected neighbours. Otherwise, the pair of neighbouring children of and are reflected neighbours.

### Remark 4.1

If and are reflected neighbours, then the pair(s) of their neighbouring children are reflected neighbours. The opposite statement, however, is not true. E.g., for and arbitrary neighbours , and are reflected neighbours when or They are already matching when . or see Figure ;3 for an illustration.

### Remark 4.2

Instead of (b), in ReferenceMau95ReferenceTra97 it was required that for any neighbouring tagged simplices and the ordered sequence of their vertices coincides on all but one position (being the definition of reflected neighbours in ReferenceTra97), which is thus an even stronger condition than being reflected neighbours in our terminology. As shown in ReferenceTra97, for a simply connected domain, it can be satisfied if and only if each hyperface not on the boundary of the domain is shared by an even number of simplices. For -dimensional it means that the valence of any interior vertex should be even. On the other hand, for , condition (b) corresponds to the condition described in ReferenceBDD04, 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 condition ,(b) can be satisfied for each conforming partition. Therefore, inspired by such a construction for in ReferenceKos94, in Appendix A we show that any conforming partition of can be refined to a conforming partition -simplices of tagged simplices of type such that any two neighbours are reflected neighbours, which is thus stronger than needed for (b).

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

### Theorem 4.3

Any uniform refinement of is conforming.

### Proof.

Since is a refinement of it satisfies ,EquationC1. Thanks to Theorem 3.2, it only remains to show that any for which , contains a point interior to a true hyperface of (or are neighbours. If ), and have the same ancestor in then this has been shown in ,ReferenceTra97, §5. Otherwise, with different ancestors and from of and respectively, , contains a point interior to a true hyperface of (or and so ), and are neighbours by (a).

If or is on then , and are reflected neighbours by (b), and so on any level the subdivision of into descendants is a reflection in of the corresponding subdivision of This is easily seen when the ordered sequences of vertices of . and coincide on all but one positions, but the same is true when the ordered sequences of vertices of and coincide on all but one positions, since and have the same children. We conclude that in this case and are neighbours.

Otherwise, (b) shows that the children of and that have as a hyperface, and thus which contain and respectively, are reflected neighbours. The same argument shows that , and 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 Indeed, since an edge is never cut on two consecutive levels, if . and as in (b) both have their refinement edge not on 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 if any of two neighbours , , have their refinement edge on then the union of their level , descendants can only form conforming partitions for any when and are reflected neighbours. Suppose they are not, meaning that the ordered sequences of vertices of both , and , differ on more than one position. It is needed that since otherwise already their level 1 descendants do not form a conforming partition. By possibly replacing , by we may assume that , and By the assumption that the ordered sequences of vertices differ on more than one position, and the fact that . and are neighbours, there exists an with and or on For each . there exists one level , descendant ( of ) ( having vertex ) ( and a true hyperface on ) So as long as for increasing . the union of the level , descendants of and form a conforming partition, and are neighbours. At some level however, depending on , and , will be cut along and along meaning that on level , the partitions are nonconforming, completing the proof of the necessity of (b).

### Remark 4.5

In ReferenceBän91ReferenceAMP00, algorithms for bisection tetrahedra, i.e., for 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 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 generated by the algorithms from ReferenceBän91ReferenceAMP00 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 starting with an arbitrary tagging of the triangles, the triangles on level 2 can always be locally retagged such that ,(b) is valid (see ReferenceBDD04, 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 and , we set ,

### Corollary 4.6

For any partition , and , either ,

- •
and are compatibly divisible, or

- •
and is compatibly divisible with one of the children of .

### Proof.

For some let , be neighbours with Then there is a level . descendant of that contains a point of interior to a true hyperface. Theorem 4.3 shows that this level descendant is a neighbour of i.e., that it has a true hyperface in common with , and thus with Since a level . descendant of has less than vertices in common with we arrive at a contradiction, and conclude that the levels of neighbours differ at most one. ,

Now let with Then again Theorem .4.3 shows that one of both children of is a neighbour of However, since . has its refinement edge on this cannot be the case.

Concerning the two remaining cases, if then , are indeed compatibly divisible, since otherwise the uniform refinement with simplices of level would not be conforming.

If then one of both children of , has a point of interior to a true hyperface, so that they are neighbours by Theorem 4.3. Since the uniform refinement with simplices of level is conforming, we conclude that this child and are compatibly divisible.

■## 5. Local refinements while retaining conformity

Let be a conforming partition, and let be a subset of simplices that have been marked for bisection. After bisecting the simplices from a generally nonconforming partition , 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 ,**complete** outputs the smallest conforming refinement of assuming that a conforming refinement exists. This, however, holds true, since with , the uniform partition with simplices of level , is a conforming refinement of 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 and then restoring conformity by a call of **complete**, is, when running over for each of those , to replace the current partition by its smallest conforming refinement in which has been bisected. A call of the routine **refine** given below determines such a partition. Since it bisects generally more simplices than only it may happen that it bisects , 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** is a generalization to of such a routine by Kossaczký in -dimensionsReferenceKos94 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 after which this set of simplices can be simultaneously bisected without introducing nonconformities. ,

### Theorem 5.1

terminates, and is the smallest conforming refinement of in which has been bisected. If is newly created by the call, then .

### Proof.

Let 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 have the same refinement edge as and satisfy , and If . then in the next iteration of the ,do-until loop, the set will be extended. Since, on the other hand, from the uniform shape regularity we know that the cardinality of is bounded, we conclude that this loop terminates. After termination, and so for all , , by Theorem ,3.2 meaning that by bisecting all conformity is retained. It is clear that we cannot confine bisection to a smaller set of simplices, and that for any newly created .

Assuming that for some the statement is true for , with let us consider , with Possible recursive calls of . are unavoidable, where Corollary 4.6 shows that The induction hypothesis then shows that such a call outputs the smallest conforming partition in which . has been bisected, and moreover, that it does not bisect any simplex that is already in since that would create simplices with levels larger than , Now the proof is completed using the same arguments as in the . case.

■Assuming that the data structures allow that the determination of requires not more than an absolute constant number of operations, note that the number of operations needed for is .

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

### Theorem 5.2

With the constant from Equation4.1, any newly created by the call satisfies

### Proof.

For any newly created , is a child of a that has its refinement edge on so that , Note that in this case the sum over . is empty since .

Assuming that the theorem holds for let us consider , with If . is created by bisection of any simplex from the set then the statement is proven as in the , case. If is created by a recursive call then using , the induction hypothesis shows that ,

by .

■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 (ReferenceSS05).

### 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 the adaptive finite element method introduced in ,ReferenceMNS00 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 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 by Binev, Dahmen and DeVore. Since there are some small modifications, we include the proof for the reader’s convenience.

### Theorem 6.1 (generalizes ReferenceBDD04, Theorem 2.4 for ).

With 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 it holds that only dependent on the constants , from Equation4.1, and .

### Proof.

Fixing let , , be some sequences with , and , Valid instances are . and Let . .

Inside this proof, will always denote the output partition of the algorithm, whereas any intermediate partition will be denoted as We define . by

For any fixed and , with there exists a uniformly bounded number, only dependent on , and of , with and In view of the definition of . we thus have , and so , .

In the second part of this proof, we are going to show that for all ,

only dependent on , and so that ,

as required.

Let For . given that , has been defined and assuming that it is not in we let , be such that has been created by the call Let . be the smallest integer such that Note that such an . exists since at some point the sequence ends with a thus with , whereas the value , cannot be passed without being attained because by Theorem 5.1. From Theorem 5.2 and Equation4.1, for we have

where denotes the number of with .

In case for all then the definition of the constant , shows that and so by definition of , we conclude that , which shows ,Equation6.1.

Otherwise, there exist with For each of those . there exists a smallest , with We denote . that gives rise to the smallest as and denote , as Thus . for all and , As in the case that . for all we find that for all , , and In view of the definition of . we find that ,

showing Equation6.1 also in this case.

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

## Appendix A. An initial refinement to satisfy condition (b)

Suppose we are given some conforming partition of Generalizing upon the construction by Kossaczký in -simplices.ReferenceKos94 for in this appendix we construct a conforming refinement of tagged simplices of type , such that any two neighbours are reflected neighbours.

We start with constructing a conforming subdivision of any into -simplex subsimplices, together with a global labeling of vertices and a marking of edges in this subdivision that satisfy the following conditions:

- •
a vertex on a marked edge has no label,

- •
the other vertices are labeled with numbers ,

- •
each subsimplex contains vertices with labels and two vertices on a marked edge,

- •
the subdivision and labeling/marking is symmetric in the barycentric coordinates of the original (macro-) simplex.

For we subdivide a triangle into three subtriangles by connecting the vertices with the centroid. This centroid is labeled with number 1, and the edges of the original (macro-) triangle are marked. Clearly, the above conditions are satisfied. ,

For assuming we have defined a valid subdivision and labeling and marking of any , we define this for an -simplex, as follows: Create -simplex subsimplices by connecting the vertices with the centroid. Label the centroid with number Each of the subsimplices shares a face with the original (macro-) simplex. Use the subdivision of any . to subdivide these faces into -simplex labeled/marked Connect the vertices on the faces with the centroid to end with a subdivision into -simplices. simplices with a valid labeling/marking. See Figure 4 for an illustration.

Returning to the given conforming partition of we subdivide each of its simplices into -simplices, subsimplices as above. Clearly this refined partition, that will serve as the initial partition is also conforming. Tagging the simplices in , means specifying a type, that will be as well as a local ordering of the vertices in each simplex. We simply let each simplex inherit the labeling of the vertices from the macro-simplex that contains it, with the addition that both vertices on the marked edge are numbered 0 and , in arbitrary order; see Figure 5 for an illustration for Neighbours within one macro-simplex are obviously reflected neighbours, since their numbering of the vertices on the hyperface between them is the same modulo permutations of 0 and . The same is valid for neighbours from different macro-simplices, because of the symmetry of the labeling in the barycentric coordinates. We conclude that . satisfies condition (b).

## Acknowledgment

The author would like to thank Dr. Michael Bader (Technische Universität München) for pointing out a serious problem with the bisection rule from an earlier version of this work.