Hierarchy of surface models and irreducible triangulations

Siu Wing Cheng, Tamal K. Dey, Sheung Hung Poon

Research output: Journal PublicationArticlepeer-review

14 Citations (Scopus)


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, a greedy strategy can identify Θ(n) topology-preserving edge contractions that do not interfere with each other. Further, each of them affects only a constant number of triangles. Repeatedly identifying and contracting such edges produces a topology-preserving hierarchy of O(n+g 2) size and O(logn+g) depth. Although several implementations exist for constructing hierarchies, our work is the first to show that a greedy algorithm can efficiently compute a hierarchy of provably small size and low depth. When no contractible edge exists, the triangulation is irreducible. Nakamoto and Ota showed that any irreducible triangulation of an orientable 2-manifold has at most max{342g-72,4} vertices. Using our proof techniques we obtain a new bound of max{240g,4}.

Original languageEnglish
Pages (from-to)135-150
Number of pages16
JournalComputational Geometry: Theory and Applications
Issue number2
Publication statusPublished - Feb 2004
Externally publishedYes


  • 2-manifold
  • Edge contraction
  • Homology
  • Irreducible triangulation
  • Level of detail

ASJC Scopus subject areas

  • Computer Science Applications
  • Geometry and Topology
  • Control and Optimization
  • Computational Theory and Mathematics
  • Computational Mathematics


Dive into the research topics of 'Hierarchy of surface models and irreducible triangulations'. Together they form a unique fingerprint.

Cite this