Hierarchy of Surface Models and Irreducible Triangulation

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\cdot g$, a greedy strategy can identify $\Theta(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(\log n + g)$
depth. In practice, the genus $g$ is very small when compared with $n$
for large models and the selection of edges can be enhanced by measuring
the error of their contractions using some known heuristics. 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\}$.