## Abstract

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 language | English |
---|---|

Pages (from-to) | 135-150 |

Number of pages | 16 |

Journal | Computational Geometry: Theory and Applications |

Volume | 27 |

Issue number | 2 |

DOIs | |

Publication status | Published - Feb 2004 |

Externally published | Yes |

## Keywords

- 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