TY - GEN
T1 - Hierarchy of surface models and irreducible triangulation
AU - Cheng, Siu Wing
AU - Dey, Tamal K.
AU - Poon, Sheung Hung
N1 - Copyright:
Copyright 2013 Elsevier B.V., All rights reserved.
PY - 2002
Y1 - 2002
N2 - 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}.
AB - 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}.
UR - http://www.scopus.com/inward/record.url?scp=84878632410&partnerID=8YFLogxK
U2 - 10.1007/3-540-36136-7_26
DO - 10.1007/3-540-36136-7_26
M3 - Conference contribution
AN - SCOPUS:84878632410
SN - 3540001425
SN - 9783540001423
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 286
EP - 295
BT - Algorithms and Computation - 13th International Symposium, ISAAC 2002, Proceedings
T2 - 13th Annual International Symposium on Algorithms and Computation, ISAAC 2002
Y2 - 21 November 2002 through 23 November 2002
ER -