TY - JOUR
T1 - Simple and optimal output-sensitive construction of contour trees using monotone paths
AU - Chiang, Yi Jen
AU - Lenz, Tobias
AU - Lu, Xiang
AU - Rote, Günter
N1 - Funding Information:
* Corresponding author. E-mail addresses: [email protected] (Y.-J. Chiang), [email protected] (T. Lenz), [email protected] (X. Lu), rote@inf. fu-berlin.de (G. Rote). 1 Research supported in part by NSF CAREER Grant CCR-0093373, NSF Grant ACI-0118915, and NSF ITR Grant CCR-0081964. 2 Partially supported by the IST Program of the EU as a Shared-cost RTD (FET Open) Project under Contract No IST-2000-26473 (ECG—Effective Computational Geometry for Curves and Surfaces). 3 Research supported by NSF Grant CCR-0093373.
PY - 2005/2
Y1 - 2005/2
N2 - 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.
AB - 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.
KW - Computational topology
KW - Level sets
KW - Piecewise linear Morse theory
UR - http://www.scopus.com/inward/record.url?scp=10044238852&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=10044238852&partnerID=8YFLogxK
U2 - 10.1016/j.comgeo.2004.05.002
DO - 10.1016/j.comgeo.2004.05.002
M3 - Article
AN - SCOPUS:10044238852
SN - 0925-7721
VL - 30
SP - 165
EP - 195
JO - Computational Geometry: Theory and Applications
JF - Computational Geometry: Theory and Applications
IS - 2 SPEC. ISS.
ER -