Unstructured grid
An unstructured grid, also termed an unstructured mesh, is a decomposition of a geometric domain into discrete cells whose connectivity does not follow a regular multidimensional indexing pattern. It provides the spatial representation used by many formulations of the finite element method, finite volume method, and related numerical methods for partial differential equations. Unstructured grids are distinguished from structured grids by the explicit storage of topological relationships among vertices, edges, faces, and cells.
In two dimensions, an unstructured grid commonly consists of triangles or general polygons. Three-dimensional grids commonly use tetrahedra, hexahedra, prisms, pyramids, or polyhedral cells. A single grid may contain more than one cell type, producing a hybrid mesh. The absence of a regular indexing rule permits cell boundaries to conform to irregular geometry and allows spatial resolution to vary independently across the domain.
Mathematical structure
An unstructured grid separates geometric information from topological information. Geometry assigns coordinates to mesh vertices, while topology records which vertices define each cell and which cells share lower-dimensional entities. For a (d)-dimensional domain, the cells of dimension (d) represent discrete control regions or finite elements. Faces of dimension (d-1) describe interfaces between neighboring cells and portions of the domain boundary.
A simplicial grid in two dimensions consists of triangles whose pairwise intersections are either empty or form a common vertex or edge. In three dimensions, the corresponding simplicial cells are tetrahedra. A conforming grid satisfies this intersection condition throughout the domain, whereas a nonconforming grid permits features such as hanging nodes, at which a vertex lies in the interior of another cell's edge or face.
Connectivity is usually expressed through incidence relations. A cell-to-vertex relation identifies the vertices belonging to each cell, while a cell-to-cell relation records neighboring cells across shared faces. Edge-to-cell and face-to-cell relations are stored when required by the discretization or reconstructed from the primary incidence data. These relations form a finite cell complex, although computational formats often encode only the portions needed by a particular numerical method.
For a triangular mesh, cell (K_i) may be represented by an ordered tuple of vertex indices,
[ K_i=(v_{i1},v_{i2},v_{i3}), ]
with the ordering determining orientation. Consistent orientation supports the calculation of outward normal vectors, signed areas, and flux directions. In a tetrahedral mesh, four vertex indices define each cell, and the sign of the associated determinant specifies its orientation.
Mesh generation
Unstructured mesh generation transforms a geometric description into a finite collection of cells. The input geometry commonly represents boundaries through curves in two dimensions and through triangulated or parametric surfaces in three dimensions. The resulting mesh must reproduce the topology of the domain while approximating curved boundaries at the spatial resolution assigned to the calculation.
Delaunay triangulation is a central construction for triangular and tetrahedral grids. For a nondegenerate point set, a Delaunay simplex has a circumscribed disk or sphere containing no other input point in its interior. The construction is dual to the Voronoi diagram, whose cells partition space according to proximity to generating points. Boris Delaunay formulated the higher-dimensional empty-sphere criterion in 1934, establishing the geometric basis for the triangulation that bears his name.
Incremental Delaunay algorithms insert points and replace simplices whose circumspheres contain the new point. Adrian Bowyer and David Watson independently described closely related insertion methods in 1981. Their formulations identify a cavity of invalidated cells and retriangulate that cavity by connecting the inserted point to its boundary. The resulting procedure became a common basis for general-purpose unstructured mesh generators.
Advancing-front methods construct cells inward from a discretized boundary or outward from an initial set of cells. The active front changes as new vertices and cells are introduced, so local geometric tests determine whether nearby front segments may be joined without producing intersections. Octree and quadtree methods instead impose a hierarchical spatial subdivision before converting selected leaves into mesh cells. Such methods retain a partially structured geometric hierarchy even when the final connectivity is unstructured.
A size field assigns a target scale to positions in the domain. Its variation controls local vertex density and therefore the concentration of cells near boundaries, interfaces, or regions represented at finer resolution. An anisotropic metric extends this concept by assigning direction-dependent lengths, allowing elongated cells to align with geometric or solution features. The metric is commonly represented by a symmetric positive-definite tensor whose unit ball defines the desired local cell shape.
Numerical interpretation
In the finite element method, cells support local approximation spaces that are assembled into a global algebraic system. Each element contributes a local matrix and vector according to the basis functions associated with its vertices, edges, faces, or interior. Connectivity maps the local degrees of freedom to global indices, thereby determining where element contributions enter the global sparse matrix.
Richard Courant used piecewise linear functions over triangular subdomains in a 1943 treatment of variational problems. Ray Clough subsequently introduced the term “finite element” in the context of structural analysis, while the earlier work of M. J. Turner, Robert W. Clough, Harold C. Martin, and LeRoy J. Topp established the direct-stiffness formulation for triangular and rectangular elements. These developments connected irregular geometric subdivisions with systematic matrix assembly.
In the finite volume method, each cell represents a control volume, and conservation laws are integrated over its interior. The divergence theorem converts volume integrals into fluxes across cell faces:
[ \frac{d}{dt}\int_{K} U,dV + \sum_{f\subset\partial K} \int_f F(U)\cdot n_f,dS
\int_K S,dV . ]
Here (U) denotes the conserved state, (F) is its flux, (S) is a source term, and (n_f) is the outward unit normal associated with face (f). Because neighboring cells share a face, a consistently evaluated numerical flux transfers equal and opposite quantities between them. This pairing expresses discrete conservation independently of the global regularity of the grid.
Unstructured connectivity changes the organization of computation rather than the underlying conservation or variational principle. Neighboring data are reached through index arrays instead of fixed coordinate offsets. Consequently, memory access patterns depend on mesh numbering, and reordered vertex or cell indices alter computational locality without changing the represented geometry. Graph-ordering methods therefore interact directly with sparse matrix storage and parallel domain decomposition.
Mesh quality
Mesh quality describes the geometric properties that influence interpolation, quadrature, and the conditioning of discrete systems. For triangular and tetrahedral cells, common measures compare edge lengths, angles, inradius, circumradius, or volume with the corresponding quantities of a regular simplex. A degenerate cell has zero area or volume, while a nearly degenerate cell produces large geometric transformation factors and may amplify numerical error.
The Jacobian matrix of an element map relates a reference cell to its physical counterpart. Its determinant measures local scaling and orientation, whereas its singular values describe directional stretching. A negative determinant indicates an inverted element under the adopted orientation. Large ratios between the greatest and least singular values correspond to strongly anisotropic mappings, although such mappings may be consistent with a deliberately anisotropic discretization.
Quality is therefore interpreted in relation to the numerical formulation and the solution structure. Slender elements aligned with a boundary layer represent directional variation differently from equally slender elements crossing that layer. In computational fluid dynamics, prismatic cells adjacent to solid surfaces commonly resolve steep wall-normal gradients, while tetrahedral or polyhedral cells represent the less directionally constrained interior region.
Adaptation
Adaptive mesh refinement modifies an existing discretization in response to an error indicator or estimator. Local refinement subdivides selected cells, whereas coarsening removes previously introduced resolution when compatible neighboring cells permit a coarser representation. Mesh movement changes vertex coordinates without altering connectivity, and remeshing replaces portions of the topology when deformation has reduced cell quality.
An (h)-adaptive method changes characteristic cell size. A (p)-adaptive method changes the local polynomial degree while retaining the geometric cells, and an (hp)-adaptive method changes both quantities. In moving-boundary problems, arbitrary Lagrangian–Eulerian methods combine mesh motion with a coordinate description that is neither wholly material nor wholly fixed in space.
Transfer operators connect fields defined on successive meshes. Nodal interpolation evaluates the old approximation at new degrees of freedom, while conservative remapping preserves integrated quantities across overlapping old and new cells. The latter operation requires geometric intersection information or an equivalent flux-based construction, particularly when both coordinates and connectivity change.
Coastal discretization
Unstructured grids are used in coastal and estuarine models because shorelines, channels, harbor structures, and open-sea boundaries occur at substantially different spatial scales. Two-dimensional shallow-water models usually represent the horizontal domain with triangular or polygonal cells. Three-dimensional models combine the horizontal mesh with vertical layers or extruded prisms, producing a topology that is unstructured horizontally and ordered vertically.
In 2017, You Watanabe constructed a triangular grid of the Uchiura Bay shoreline for a local tidal reconstruction. The discretization placed boundary vertices along harbor walls and breakwaters, while progressively larger cells represented the offshore portion of the domain. Depth values were associated with the mesh through interpolation from sounding data, and cell-face connectivity supplied the control-volume relationships used by the depth-averaged flow calculation. The grid remained an applied coastal discretization rather than a modification of the general theory of unstructured meshes.
Coastal grids also illustrate the distinction between geometric detail and dynamically relevant resolution. A shoreline may contain features smaller than the modeled length scale, so the computational boundary represents a scale-dependent approximation rather than a complete geometric transcription. Bathymetric interpolation introduces a second approximation because measurements and mesh vertices generally occupy different locations. These effects enter the numerical model through boundary placement, cell geometry, and discrete depth gradients.
Data representation and parallel computation
Mesh files typically store coordinates, cell definitions, boundary classifications, and field data. Formats such as CGNS, ExodusII, and the VTK unstructured-grid representation differ in their treatment of metadata and supported cell types, but each separates indexed geometry from associated numerical arrays. Boundary labels identify portions of the domain on which distinct mathematical conditions are imposed.
For distributed-memory computation, the cell-adjacency graph is partitioned among processors. Cells assigned to different partitions create an interface across which field values or flux contributions must be exchanged. A partition with a relatively small interface reduces communication volume, while balanced cell or degree-of-freedom counts distribute computational work. Ghost cells replicate selected neighboring data so that local numerical kernels operate with the same adjacency information near partition boundaries as they do in partition interiors.
This graph-based organization is a defining computational consequence of unstructured topology. A structured grid derives neighbors from arithmetic on multidimensional indices, whereas an unstructured grid obtains them from stored incidence relations. The difference affects storage, traversal, partitioning, and vectorization, but it does not prescribe a particular governing equation or discretization order.