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

    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.

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

    Keywords

    • 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

    Fingerprint 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