I am currently working on a 2D finite element code with a mesh that contains duplicate nodes at certain interfaces where jumps occur. In order to set up the appropriate linear systems, I have to take the mesh connectivity information and locations of mesh nodes, and manipulate them to determine which elements are adjacent across an interface.

To get an idea of potential run-time scaling in serial, I've expressed all of the asymptotic complexities of each algorithm in terms of the number of nodes (or the number of degrees of freedom), because that is a natural complexity metric. I'm able to do that using well-known facts about planar graphs.

I'd like to be able to extend these algorithms to 3D meshes, and I'd like to have an idea of their complexity in terms of the number of nodes. I'm also sure that 3D meshes are not necessarily planar graphs. Is there a result that bounds the number of edges, facets, and elements of a 3D mesh in terms of the number of mesh nodes? Assuming a simplicial mesh is fine; results for hexahedral meshes would also be interesting, too.

I'm sure that none of what I'm doing is new; I just don't work with meshes very much, so I have no idea where to look for the result.


2 Answers 2


The complexity of simplicial tessellations in $\mathbb{R}^{d}$, for $d>2$ is, unfortunately, not linear.

In general, a simplicial tessellation $\mathcal{T}(X)$ for $n$ vertices $X\subset\mathbb{R}^{d}$ can have $\Theta(n^{\lceil d/2\rceil})$ d-simplexes in the worst case. Similar results exist for the lower dimensional faces of $\mathcal{T}$.

Based on practical experience with tetrahedral meshes in $\mathbb{R}^{3}$ though, I think it's generally accepted that most tetrahedral meshes exhibit linear complexity, such that $|\mathcal{T}|=O(n)$. Considering that you're almost certainly dealing with a high quality finite-element style mesh, rather than some contrived pathological example from computational geometry, I imagine that linear complexity would be observed in practice in your case.

You might be interested to check out Jonathan Shewchuk's research on (Delaunay) tessellations. The result quoted above appears in the recent book Delaunay Mesh Generation by Shewchuk, Cheng and Dey -- it's a great reference for mesh generation theory!


For 2D and triangles, there's the traditional Euler formula:

$$ E=F+V-1 $$

for $E$ edges, $F$ faces, and $V$ vertices (assuming no holes).

In 3D on tetrahedra, there's a similar formula:

$$ V-E+F=T+1 $$

where everything is as above with $T$ tets. This is all taken from Carey's book Computational Grids, Taylor & Francis, 1997 pp. 86 and 90.

As Darren's answer points out, though, this can lead to some complexity in 3D, though many meshes are nice.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.