Contour Tree Computation

The oldest strand of my research involves computing the contour tree or Reeb graph. This captures the relationships between the contours of a function, and therefore the relationships between maxima (peaks) and minima (pits). For data defined over a simple block of space, it is guaranteed to be a tree, which makes it a lot easier to compute.

image: contour_trees_vancouver

My M.Sc. thesis gave what is now the standard serial algorithm for computing the contour tree, and provided a foundation for most of my research since. This was awarded the Test of Time Award by the Computational Geometry journal in 2022:

This also involved exploiting the contour tree to extract path seeds to accelerate contour/isosurface extraction,

and mechanisms to adapt the algorithm to various types of mesh:

Contour Tree Computation