Yi-Jen Chiang, Tobias Lenz, Xiang Lu, and Günter Rote:

1. Simple and output-sensitive construction of contour trees using monotone paths

2. Simple and optimal output-sensitive construction of contour trees using monotone paths

Abstract

Contour trees are used when high-dimensional data are preprocessed for efficient extraction of iso-contours for the purpose of visualization. So far, efficient algorithms for contour trees are based on processing the data in sorted order. We present a new algorithm that avoids sorting the whole data set, but sorts only the component-critical points. They form only a small fraction of the points, for typical data that arise in practice. The algorithm works in any dimension.

In addition, we provide a comprehensive discussion of critical and regular points of piecewise linear functions of two and three variables.