Compact Representations of Simplicial Meshes in Two and Three Dimensions

We describe data structures for representing simplicial meshes compactly while supporting online queries and updates efficiently. Our representation requires about a factor of five times less memory than the most efficient standard representations of triangular or tetrahedral meshes, while efficiently supporting traversal among simpices, storing data on simpices, and insertion and deletion of simplices. Our implementation of the data structures uses about 5 bytes/triangle in two dimensions (2D) and 7.5 bytes/tetrahedron in three dimensions (3D). We use the representations to implement 2D and 3D incremental algorithms for generating a Delaunay mesh. The 3D algorithm can generate 100 Million tetrahedrons with 1 Gbyte of memory, including the space for the coordinates and all data used by the algorithm. The runtime of the algorithm is as fast a Shewchuk's Pyramid code, the most efficient we know of, and uses a factor of 3.5 less memory overall.