carrier image

Representing Simplicial Complexes with Mangroves

Canino, David and Leila De Floriani

22nd International Meshing Roundtable, Springer-Verlag, pp.465-483, October 13-16 2013


22nd International Meshing Roundtable
Orlando, FL
October 13-16,2013

Department of Computer Science, Bioengineering, Robotics and Systems Engineering (DIBRIS), University of Genova, Genova, Italy
Email: {canino,deflo}

Simplicial complexes are extensively used for discretizing digital shapes in two, three, and higher dimensions within a variety of application domains. There have been many proposals of topological data structures, which represent the connectivity information among simplices. We introduce the Mangrove Topological Data Structure (Mangrove TDS) framework, a tool which supports the efficient implementation of data structures for simplicial complexes of any dimension under the same application interface. Our framework is based on a graph-based representation of connectivity relations, that we call the mangrove. It can be customized in order to simulate the content of any topological data structure with a negligible overhead. Thus, the Mangrove TDS framework is extensible, and supports the most diverse modeling needs. We also provide implicit representations of those simplices, which are not directly encoded in a specific topological data structure. Our tests show that these representations, that we call ghost simplices, improve the expressive power and the efficiency of topological queries. In order to prove the validity of our approach, we design two topological data structures, specific for non-manifold complexes, within our framework. We perform comparisons with some widely-used representations in the literature as well as with libraries available in the public domain.

Download Full Paper (PDF Format)

Contact author(s) or publisher for availability and copyright information on above referenced article