Spatial indexing on tetrahedral meshes

TitleSpatial indexing on tetrahedral meshes
Publication TypeConference Papers
Year of Publication2010
AuthorsDe Floriani L, Fellegara R, Magillo P
Conference NameProceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems
Date Published2010///
Conference LocationNew York, NY, USA
ISBN Number978-1-4503-0428-3
Keywordskd-trees, octrees, spatial indexes, tetrahedral meshes

We address the problem of performing spatial queries on tetrahedral meshes. These latter arise in several application domains including 3D GIS, scientific visualization, finite element analysis. We have defined and implemented a family of spatial indexes, that we call tetrahedral trees. Tetrahedral trees subdivide a cubic domain containing the mesh in an octree or 3D kd-tree fashion, with three different subdivision criteria. Here, we present and compare such indexes, their memory usage, and spatial queries on them.