IA*: An adjacency-based representation for non-manifold simplicial shapes in arbitrary dimensions

TitleIA*: An adjacency-based representation for non-manifold simplicial shapes in arbitrary dimensions
Publication TypeJournal Articles
Year of Publication2011
AuthorsCanino D, De Floriani L, Weiss K
JournalComputers & Graphics
Volume35
Issue3
Pagination747 - 753
Date Published2011/06//
ISBN Number0097-8493
KeywordsNon-manifold data structures, simplicial complexes, Topological data structures
Abstract

We propose a compact, dimension-independent data structure for manifold, non-manifold and non-regular simplicial complexes, that we call the Generalized Indexed Data Structure with Adjacencies (IA⁎ data structure). It encodes only top simplices, i.e. the ones that are not on the boundary of any other simplex, plus a suitable subset of the adjacency relations. We describe the IA⁎ data structure in arbitrary dimensions, and compare the storage requirements of its 2D and 3D instances with both dimension-specific and dimension-independent representations. We show that the IA⁎ data structure is more cost effective than other dimension-independent representations and is even slightly more compact than the existing dimension-specific ones. We present efficient algorithms for navigating a simplicial complex described as an IA⁎ data structure. This shows that the IA⁎ data structure allows retrieving all topological relations of a given simplex by considering only its local neighborhood and thus it is a more efficient alternative to incidence-based representations when information does not need to be encoded for boundary simplices.

URLhttp://www.sciencedirect.com/science/article/pii/S0097849311000483
DOI10.1016/j.cag.2011.03.009