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

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

    Research output: Contribution to journalArticlepeer-review


    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.

    Original languageEnglish (US)
    Pages (from-to)165-195
    Number of pages31
    JournalComputational Geometry: Theory and Applications
    Issue number2 SPEC. ISS.
    StatePublished - Feb 2005


    • Computational topology
    • Level sets
    • Piecewise linear Morse theory

    ASJC Scopus subject areas

    • Computer Science Applications
    • Geometry and Topology
    • Control and Optimization
    • Computational Theory and Mathematics
    • Computational Mathematics


    Dive into the research topics of 'Simple and optimal output-sensitive construction of contour trees using monotone paths'. Together they form a unique fingerprint.

    Cite this