A data structure for non-manifold simplicial d-complexes

Floriani, Leila De; Greenfieldboyce, David; Hui, Annie

A data structure for non-manifold simplicial d-complexes

Files

085-094.pdf (169.53 KB)

Date

2004

Authors

Floriani, Leila De
Greenfieldboyce, David
Hui, Annie

Publisher

The Eurographics Association

Abstract

We propose a data structure for d-dimensional simplicial complexes, that we call the Simplified Incidence Graph (SIG). The simplified incidence graph encodes all simplices of a simplicial complex together with a set of boundary and partial co-boundary topological relations. It is a dimension-independent data structure in the sense that it can represent objects of arbitrary dimensions. It scales well to the manifold case, i.e. it exhibits a small overhead when applied to simplicial complexes with a manifold domain. Here, we present efficient navigation algorithms for retrieving all topological relations from a SIG, and an algorithm for generating a SIG from a representation of the complex as an incidence graph. Finally, we compare the simplified incidence graph with the incidence graph, with a widely-used data structure for d-dimensional pseudo-manifold simplicial complexes, and with two data structures specific for two- and three-dimensional simplicial complexes.

        @inproceedings{:10.2312/SGP/SGP04/085-094
,
booktitle = {Symposium on Geometry Processing
},
editor = {Roberto Scopigno and Denis Zorin
},
title = {{A data structure for non-manifold simplicial d-complexes
}},
author = {Floriani, Leila De and 
Greenfieldboyce, David and 
Hui, Annie
},
year = {2004
},
publisher = {The Eurographics Association
},
ISSN = {1727-8384
},
ISBN = {3-905673-13-4
},
DOI = {/10.2312/SGP/SGP04/085-094
}
}