10.1184/R1/6604226.v1 Daniel K. Blandford Daniel K. Blandford Guy E. Blelloch Guy E. Blelloch David E. Cardoze David E. Cardoze Clemens Kadow Clemens Kadow Compact Representations of Simplicial Meshes in Two and Three Dimensions Carnegie Mellon University 2005 mesh representations computational geometry compression 2005-01-01 00:00:00 Journal contribution https://kilthub.cmu.edu/articles/journal_contribution/Compact_Representations_of_Simplicial_Meshes_in_Two_and_Three_Dimensions/6604226 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.