Proceedings of the 20th Annual ACM Symposium on Computational Geometry, 300-309, 2004.
We propose a new algorithm for constructing finite-element meshes suitable for spacetime discontinuous Galerkin solutions of linear hyperbolic PDEs. Given a triangular mesh M of some planar domain and a target time value T, our method constructs a tetrahedral mesh of the spacetime domain M×[0,T], in constant time per element, using an advancing front method. Elements are added to the evolving mesh in small patches by moving a vertex of the front forward in time. Spacetime discontinuous Galerkin methods allow the numerical solution within each patch to be computed as soon as the patch is created. Our algorithm employs new mechanisms for adaptively coarsening and refining the front in response to a posteriori error estimates returned by the numerical code. A change in the front induces a corresponding re nement or coarsening of future elements in the spacetime mesh. Our algorithm adapts the duration of each element to the local quality, feature size, and degree of refinement of the underlying space mesh. We directly exploit the ability of discontinuous Galerkin methods to accommodate discontinuities in the solution fields across element boundaries.