Hierarchy of surface models and irreducible triangulations. (Q1428114)

This paper deals with surface simplification in computer graphics. The problem of computing the hierarchy of surface triangulations is related to a mathematical question.An edge is contractible if its contraction does not change the surface topology. A triangulation of a 2-manifold is called irreducible if no edge is contractible. Is there an upper bound on the number of vertices of an irreducible triangulation in terms of the genus \(g\)? In 1989 it was proved that a finite upper bound exists. Later some such bounds are given. In this paper using a new proof technique a better upper bound of \(240g\) on the number of vertices of an irreducible triangulation is proved. By using the new techniques and by considering a maximal matching of contractible edges, the authors prove that for any constant \(d\geq444\), if \(n>9182g-222\), a greedy strategy can identify at least \[ \frac{n-1310g+30}{64\left(d+1\right)} \] independent topology-preserving edge contractions. Each edge contraction affects at most \(d+2\) triangles.. This produces a topology-preserving hierarchy of \(O(n+g^2)\) size and \(O(\log n+g)\) depth. The results are applicable to triangulations with curved edges and curved triangles. This work is the first to show that a greedy algorithm can efficiently compute a hierarchy of provably small size and low depth.