Spatial Indexes for Simplicial and Cellular Meshes

We address the problem of performing spatial and topological queries on simplicial and cellular meshes. These arise in several application domains including 3D GIS, scientific visualization and finite element analysis. Firstly, we present a family of spatial indexes for tetrahedral meshes, that we call tetrahedral trees. Then, we present the PR-star octree, that is a combined spatial data structure for performing efficient topological queries on simplicial meshes. Finally, we propose to extend these frameworks to arbitrary dimensions and to larger class of meshes, such as non-simplicial meshes.