Simplicial grid refinement: on Freudenthal's algorithm and the optimal number of congruence classes

Summary. In the present paper we investigate Freudenthal's simplex refinement algorithm which can be considered to be the canonical generalization of Bank's well known red refinement strategy for triangles. Freudenthal's algorithm subdivides any given (n)-simplex into subsimplices, in such a way that recursive application results in a stable hierarchy of consistent triangulations. Our investigations concentrate in particular on the number of congruence classes generated by recursive refinements. After presentation of the method and the basic ideas behind it, we will show that Freudenthal's algorithm produces at most n!/2 congruence classes for any initial (n)-simplex, no matter how many subsequent refinements are performed. Moreover, we will show that this number is optimal in the sense that recursive application of any affine invariant refinement strategy with sons per element results in at least n!/2 congruence classes for almost all (n)-simplices. Received February 23, 1998/ Revised version received December 9, 1998 / Published online January 27, 2000