Hierarchy of surface models and irreducible triangulation

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

Research output: Chapter in Book/Conference proceedingConference contributionpeer-review


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 + g2) size and O(logn + g) 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
Title of host publicationAlgorithms and Computation - 13th International Symposium, ISAAC 2002, Proceedings
Number of pages10
Publication statusPublished - 2002
Externally publishedYes
Event13th Annual International Symposium on Algorithms and Computation, ISAAC 2002 - Vancouver, BC, Canada
Duration: 21 Nov 200223 Nov 2002

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2518 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference13th Annual International Symposium on Algorithms and Computation, ISAAC 2002
CityVancouver, BC

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


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

Cite this