carrier image

The Efficient Location of Neighbors for Locally Refined n-Simplicial Grids

Maubach, Joseph M.

5th International Meshing Roundtable, Sandia National Laboratories, pp.137-156, October 1996


Grids of n-simplices frequently form a key ingredient when problems are modeled mathematically. In two and three space dimensions, such grids of triangles (respectively tetrahedrons) are used for the finite element approximation of solutions of partial differential equations (PDES), as in Kikuchi and Oden [24]. In more dimensions, n-simplices are used to approximate solution manifolds of parametrized equations (see Allgower and Georg [2] and Rheinboldt [39]) as well as for fixed point approximations of functions (see Todd [48]). Some types of simplical methods may also efficiently replace quadtree and octree representations of graphical data for post processing purposes, or for fractal image compression techniques, as shown in Hebert [23]. Finally, n-volume subdivision techniques are used for numerical integration purposes, as shown in Georg and Widmann [22], Allgower et al. [3] and Zumbusch in [49].

This paper presents a highly efficient bisection technique suited for the creation of adaptively refined grids of n-simplices, for any dimension n. This method, introduced first by the author in Maubach [32] is very efficient due to its simplicity: The edge to be bisected of a selected simplex is entirely determined by the manner its vertices are numbered. The method was shown to generate a bounded number of similarity classes of simplices, independent on amount of repeated bisection refinement.

Here, we consider in detail the location of the neighbors of a to be refined simplex. The location problem is part of the author's bisection algorithm, but is also of interest of its own. This problem may also occur when a convex simplicial hull is constructed step-by-step from sequentially generated points, with the use of a Delaunay method, see Bem et al. [13] Schroeder and Shephard [44], Preparato and Shamos [38] and Edelsbrunner [18].

Neighbors are of interest related to the author's bisection refinement, which bisects simplices simultaneously with a selected group of neighbors. For the n- dimensional case, n > 1, we will first indicate how to find numbers of neighbor simplices for a special but frequently used coarse initial grid. Afterwards, we will indicate how to find neighbor numbers for all newly created children in a set of so called compatible parents. Finally, we demonstrate that the set of all compatible simplices which share an edge to be bisected, can be characterized with the use of a connected n-2-simplicial surface.

Download Full Paper (PDF)

Contact author(s) or publisher for availability and copyright information on above referenced article