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

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

Technical report ECG-TR-244300-01, May 2003, 21 pages.

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

Computational Geometry, Theory and Applications 30 (2005), 165-195. doi:10.1016/j.comgeo.2004.05.002

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.

  PostScript file (gzipped)   pdf file
other papers about this subject
Last update: January 11, 2005.