A Caltech Library Service

Computational Topology Algorithms for Discrete 2-Manifolds


Wood, Zoë Justine (2003) Computational Topology Algorithms for Discrete 2-Manifolds. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/BQT9-SS34.


This thesis presents computational topology algorithms for discrete 2-manifolds. Although it is straightforward to compute the genus of a discrete 2-manifold, this topological invariant does not tell us enough for most computer graphics applications where we would like to know: what does the topology look like? Genus is a scalar value with no associated geometric appearance. We can, however, isolate geometric regions of the surface that are topologically interesting. The simplest topologically interesting, and perhaps most intuitive, regions to consider are those with genus equal to one. By isolating and examining such regions we can compute measures to better describe the appearance of relevant surface topology. Thus, this work focuses on isolating handles, regions with genus equal to one, in discrete 2-manifolds.

In this thesis, we present novel algorithms guaranteed to identify and isolate handles for various discrete surface representations. Additionally, we present robust techniques to measure the geometric extent of handles by identifying two locally minimal-length non-separating cycles for each handle. We also present algorithms to retain or simplify the topology of a reconstructed surface as desired. Finally, the value of these algorithms is demonstrated through specific applications to computer graphics. For example, we demonstrate how geometric models can be greatly improved through topology simplification both for models represented by volume data or by triangle meshes.

The contributions of this work include:

  • A robust and efficient method for identifying and isolating handles for discrete 2-manifolds.
  • A method to robustly represent the topology of the surface with an augmented Reeb graph.
  • A robust method to find two locally minimal-length non-separating cycles for each handle.
  • A simple method to simplify the topology for volume data and triangle meshes which preserves the local geometry as much as possible.
  • An out-of-core method for topology simplification for volume data.

Item Type:Thesis (Dissertation (Ph.D.))
Subject Keywords:computational topology; computer graphics; surface reconstruction; topological artifacts
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Computer Science
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Schroeder, Peter
Thesis Committee:
  • Schroeder, Peter (chair)
  • Barr, Alan H.
  • Hoppe, Hugues
  • Desbrun, Mathieu
  • Perona, Pietro
Defense Date:16 May 2003
Record Number:CaltechETD:etd-05302003-161403
Persistent URL:
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:2297
Deposited By: Imported from ETD-db
Deposited On:04 Jun 2003
Last Modified:14 Oct 2021 21:40

Thesis Files

PDF - Final Version
See Usage Policy.


Repository Staff Only: item control page