One of the major steps in the adaptive finite element methods (AFEM) is the adaptive selection of the next partition. The process is usually governed by a strategy based on carefully chosen local error indicators and aims at convergence results with optimal rates. One can formally relate the refinement of the partitions with growing an oriented graph or a tree. Then each node of the tree/graph corresponds to a cell of a partition and the approximation of a function on adaptive partitions can be expressed trough the local errors related to the cell, i.e., the node. The total approximation error is then calculated as the sum of the errors on the leaves (the terminal nodes) of the tree/graph and the problem of finding an optimal error for a given budget of nodes is known as tree approximation. Establishing a near-best tree approximation result is a key ingredient in proving optimal convergence rates for AFEM.

The classical tree approximation problems are usually related to the so-called h-adaptive approximation in which the improvements a due to reducing the size of the cells in the partition. This talk will consider also an extension of this framework to hp-adaptive approximation allowing different polynomial spaces to be used for the local approximations at different cells while maintaining the near-optimality in terms of the combined number of degrees of freedom used in the approximation.

The problem of conformity of the resulting partition will be discussed as well. Typically in AFEM, certain elements of the current partition are marked and subdivided together with some additional ones to maintain desired properties of the partition like conformity. This strategy is often described as “mark → subdivide → complete”. The process is very well understood for triangulations received via newest vertex bisection procedure. In particular, it is proven that the number of elements in the final partition is limited by constant times the number of marked cells. This hints at the possibility to design a marking procedure that is limited only to cells of the partition whose subdivision will result in a conforming partition and therefore no completion step would be necessary. This talk will present such a strategy together with theoretical results about its near-optimal performance.