Contour trees and small seed sets for isosurface traversal
Marc J. van Kreveld, René van Oostrum, Chandrajit Bajaj, Valerio Pascucci, Dan Schikore · 1997
For 2D or 3D meshes that represent a continuous function to the reals, the contours---or isosurfaces---of a specified value are an important way to visualize it. To find such contours, a seed set can be used for the starting points from which the traversal of the contours can start. This paper gives the first methods to obtain seed sets that are provably small in size. They are based on a variant of the contour tree (or topographic change tree). We give a new, simple algorithm to compute such a tree in regular and irregular meshes that requires O(n log n) time in 2D for meshes with n elements, and in O(n 2 ) time in higher dimensions. The additional storage overhead is proportial to the maximum size of any contour (linear in the worst case, but typically less). Given the contour tree, a minimum size seed set can be computed in polynomial time and storage. Since in practice at most linear storage is allowed, we develop a simple approximation algorithm giving a seed set of size at most...