A parallel and memory efficient algorithm for constructing the contour tree.

Aditya Acharya

Abstract

The contour tree is a topological structure associated with a scalar function that tracks the connectivity of the evolving level sets of the function. It efficiently stores the topological highlights of the scalar function and supports intuitive and interactive visual exploration and analysis. This thesis describes a fast, parallel, and memory efficient algorithm for constructing the contour tree of a scalar function on shared memory systems. Comparisons with existing implementations show significant improvement in both the running time and the memory expended. We observe near linear scaling of our implementation with increasing number of processors. The proposed algorithm is also particularly suited for large data sets that do not fit in memory. For example, the contour tree for a scalar function defined on a 8.6 billion vertex domain (2048 x 2048 x 2048 volume data) can be efficiently constructed using less than 10GB of memory.

[PDF]