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: yjc@poly.edu (Y.-J. Chiang), tlenz@inf.fu-berlin.de (T. Lenz), xlu@photon.poly.edu (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

VL - 30

SP - 165

EP - 195

JO - Computational Geometry: Theory and Applications

JF - Computational Geometry: Theory and Applications

SN - 0925-7721

IS - 2 SPEC. ISS.

ER -