The common mathematical basis underlying all incarnations of grids can be captured by the notions of combinatorial topology (see e. g. (13)) and polytope theory (20). Without going into the details (which can be found in (4)), we introduce some basic terminology, necessary to understand the following.
A simple 2-dimensional grid is shown in figure 2(a). It consists of just two cells, five edges and four vertices. The core of any representation in a computer is formed by the grid's combinatorial structure (fig. 2(b)), namely the incidence relationships between its elements (that is, vertices, edges and cells). Two elements are incident of one is contained in the boundary of the other; for example, is incident to , and , and vice versa. This relationship is reflected in the lattice 2(b), which is, roughly spoken, the graph of incidences.
These notions generalize easily to higher dimensions, the three-dimensional case being by far the most important one. A grid of dimension consists of elements of dimension 0 (vertices - ), dimension (edges - ), up to dimension (cells - ). The boundary of an element must be composed of lower-dimensional elements (e. g. the boundary of consists of ); and the intersection of any two elements must be another element or empty. The mathematical term for such a structure is CW-complex.
We call elements of dimension (co-dimension ) facets, which for coincides with edges. The reason for this additional name is, that many algorithms can be formulated in a dimension-independent way by using the codimension-related terms cell and facet.
Grids may differ in the pattern of incidence relationship they allow, for instance, a Cartesian grid has a very rigid checkerboard pattern, whereas unstructured grids allow for general cell types and connectivity (fig. 1).
In addition to these combinatorial properties, a grid bears also geometric information: it is embedded into some geometric space. The most common case is a planar straight line embedding; other possibilities are curved elements or embeddings into higher dimensional space or into a manifold, for example the surface of a sphere. Straight line embeddings (cf. figs 1 and 2(a)) can be represented by simply assigning space coordinates to vertices. General embeddings, however, are representable only in an approximate way, which is in sharp contrast to the combinatorial information.
Thus, it proves advantageous to preserve the separation of combinatorial and geometric aspects also in the software design, leading to a variety of combinations of the corresponding representations.
Finally, a mathematical concept often overlooked is that
of a function on the (discrete) set of grid elements,
yielding values of some arbitrary type .
Such grid functions are extremely important to almost
every algorithm on grids.
Yet they are often provided only
half-heartedly or in an ad-hoc fashion,
that depends on the needs of the concrete algorithms
to be supported.
After clarification of the mathematical concepts, a second step consists in the analysis of representative grid algorithms. It turns out that many of them pose rather modest requirements on functionality of grid data structures, which can be captured by a small set of concepts.
A typical algorithm is the determination of the total flux
into a cell across its boundary.
Performed for all cells of a grid ,
this is the core of the finite volume (FV) method:
What kind of functionality does this algorithm require?
We must iterate over all cells of a grid,
as well as over all facets of a cell,
and associate states and flux to cells.
That is, and flux are grid functions on cells.
Moreover, in numerical_flux(),
geometric data
like cell centers, facet volumes and normals are required (not shown).
We note that the algorithm above is formulated in a dimension independent way
(except, of course, the interior of the routine numerical_flux()).
In general, the requirements of most algorithms on grid data structures can be grouped as follows: