DLR-Logo -> http://www.dlr.de
DLR Portal Home | Imprint | Privacy Policy | Contact | Deutsch
Fontsize: [-] Text [+]

Tetrahedral Trees: A Family of Hierarchical Spatial Indexes for Tetrahedral Meshes

Fellegara, Riccardo and De Floriani, Leila and Magillo, Paola and Weiss, Kenneth (2020) Tetrahedral Trees: A Family of Hierarchical Spatial Indexes for Tetrahedral Meshes. ACM Transactions on Spatial Algorithms and Systems, 6 (4). Association for Computing Machinery (ACM). doi: 10.1145/3385851. ISSN 2374-0353.

[img] PDF - Only accessible within DLR - Postprint version (accepted manuscript)

Official URL: https://doi.org/10.1145/3385851


We address the problem of performing efficient spatial and topological queries on large tetrahedral meshes with arbitrary topology and complex boundaries. Such meshes arise in several application domains, such as 3D Geographic Information Systems (GISs), scientific visualization, and finite element analysis. To this aim, we propose Tetrahedral trees, a family of spatial indexes based on a nested space subdivision (an octree or a kD-tree) and defined by several different subdivision criteria. We provide efficient algorithms for spatial and topological queries on Tetrahedral trees and compare to state-of-the-art approaches. Our results indicate that Tetrahedral trees are an improvement over R*-trees for querying tetrahedral meshes; they are more compact, faster in many queries, and stable at variations of construction thresholds. They also support spatial queries on more general domains than topological data structures, which explicitly encode adjacency information for efficient navigation but have difficulties with domains with a non-trivial geometric or topological shape.

Item URL in elib:https://elib.dlr.de/138164/
Document Type:Article
Title:Tetrahedral Trees: A Family of Hierarchical Spatial Indexes for Tetrahedral Meshes
AuthorsInstitution or Email of AuthorsAuthor's ORCID iD
Fellegara, RiccardoUNSPECIFIEDhttps://orcid.org/0000-0002-8758-2802
De Floriani, LeilaUNSPECIFIEDhttps://orcid.org/0000-0002-1361-2888
Magillo, PaolaUNSPECIFIEDhttps://orcid.org/0000-0001-5088-034X
Weiss, KennethUNSPECIFIEDhttps://orcid.org/0000-0001-6649-8022
Date:June 2020
Journal or Publication Title:ACM Transactions on Spatial Algorithms and Systems
Refereed publication:Yes
Open Access:No
Gold Open Access:No
In ISI Web of Science:Yes
Publisher:Association for Computing Machinery (ACM)
Keywords:spatial indexes, octrees, topological queries, spatial queries, kD-trees, Tetrahedral meshes
HGF - Research field:Aeronautics, Space and Transport
HGF - Program:Space
HGF - Program Themes:Space System Technology
DLR - Research area:Raumfahrt
DLR - Program:R SY - Space System Technology
DLR - Research theme (Project):R - Vorhaben SISTEC (old)
Location: Braunschweig
Institutes and Institutions:Institute for Software Technology > Software for Space Systems and Interactive Visualisation
Institute for Software Technology
Deposited By: Fellegara, Dr Riccardo
Deposited On:27 Nov 2020 10:58
Last Modified:27 Nov 2020 10:58

Repository Staff Only: item control page

Help & Contact
electronic library is running on EPrints 3.3.12
Website and database design: Copyright © German Aerospace Center (DLR). All rights reserved.