Please use this identifier to cite or link to this item:

Hierarchy of surface models and irreducible triangulation

Authors Cheng, Siu-Wing
Dey, Tamal K.
Poon, Sheung-Hung
Issue Date 2002
Summary Given a triangulated closed surface, the problem of constructing a hierarchy of surface models of decreasing level of detail has attracted much attention in computer graphics. A hierarchy provides view-dependent refinement and facilitates the computation of parameterization. For a triangulated closed surface of n vertices and genus g, we prove that there is a constant c > 0 such that if n > c⋅g, then a greedy strategy can identify Θ(n) topology-preserving edge contractions that do not interfere with each other. Further, they affect only a constant number of triangles. Repeatedly identifying and contracting such edges produces a topology-preserving hierarchy of O(n + g2) size and O(log n + g) depth. The genus g is very small when compared with n for large models in practice. The identification of edges can be enhanced by selecting edges based on the error of their contractions as measured by some known heuristics. This will keep the geometric approximation small in practice. Although several implementations exist for constructing hierarchies, our work is the first to show that a greedy algorithm can efficiently compute a provably good hierarchy. When no contractible edge exists, the triangulation is irreducible. The best known upper bound on the number of vertices of an irreducible triangulation of an orientable 2-manifold is 342g - 72 by Nakamoto and Ota. Using our proof techniques we obtain a new bound of 240g.
Language English
Format Technical report
Files in this item:
File Description Size Format
200206.pdf 164241 B Adobe PDF