Topological 3D-manifolds: a statistical study of the cells
In the field of Geometric Modelling, as well as in theoretical physics, 2- and 3-combinatorial manifolds are often manipulated. Statistics on the cells of these manifolds are necessary in Geometric Modeling for the complexity analysis of data structures and algorithms dealing with these manifolds. These statistics are known in the 2D case. We study here the 3D case. We consider the set of combinatorial manifolds of dimension 3. without boundary, and with a fixed number V of vertices, E of edges, F of faces, and W of volumes (number of cells of different dimensions), and the average number of edges (resp. faces, volumes) by vertex, the average number of volumes by edge, the average number of vertices by face,and the average number of vertices (resp. of edges, faces) by volume. These quantities are shown to be sufficient to determine all the other quantities studied in this paper. We give some relations between these quantities. We give several expressions of the total number of cells, and the distribution of number of cells in relation with their dimension, with respect to some of these quantities. For the 3-G-map representations of these manifolds we also express the number of darts with respect to these quantities. And we add some hypothesis : H1 : all vertices are orientable and have the same genus G' (i.e. the dual of each vertex has a genus G'); H2 : all volumes are orientable and have the same genus G. We study the consequences of H1 and H2 on the above relations. Particularly, we obtain a general Euler formula: V(1 - G') - E + F - W(1 - G) = 0. At last, we study various particular cases of manifolds without boundary, quite regular, and their barycentric triangulations. We also show the following experimental law : when one represents a 3-manifold without boundary by a 3-G-map, the number of darts is about or exactly 6 times the number of cells. (C) 2000 Elsevier Science B.V. All rights reserved.
manifold geometric modeling complexity analysis topology based geometric modeling combinatorial topology euler-poincare formula g-map computational geometry