Automatic generation of octree-based three-dimensional discretizations forPartition of Unity methods

The Partition of Unity Method (PUM) can be used to numerically solve a set of differential equations on a domain Omega. The method is based on the def inition of overlapping patches Omega(i) comprising a cover {Omega(i)} of th e domain Omega. For an efficient implementation it is important that the in teraction between the patches themselves, and between the patches and the b oundary, is well understood and easily accessible during runtime of the pro gram. We will show that an octree representation of the domain with a tetra hedral mesh at the boundary is an efficient means to provide the needed inf ormation. It subdivides an arbitrary domain into simply shaped topological objects (cubes, tetrahedrons) giving a non-overlapping discrete representat ion of the domain on which efficient numerical integration schemes can be e mployed. The octants serve as the basic unit to construct the overlapping p artitions. The structure of the octree allows the efficient determination o f patch interactions.