Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10327453 | Computational Geometry | 2005 | 31 Pages |
Abstract
Contour trees are used when high-dimensional data are preprocessed for efficient extraction of isocontours 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 of the whole dataset, but sorts only a subset of so-called component-critical points. They form only a small fraction of the vertices in the dataset, for typical data that arise in practice. The algorithm is simple, achieves the optimal output-sensitive bound in running time, and works in any dimension. Our experiments show that the algorithm compares favorably with the previous best algorithm.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Yi-Jen Chiang, Tobias Lenz, Xiang Lu, Günter Rote,