## 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 language | English (US) |
---|---|

Pages (from-to) | 165-195 |

Number of pages | 31 |

Journal | Computational Geometry: Theory and Applications |

Volume | 30 |

Issue number | 2 SPEC. ISS. |

DOIs | |

State | Published - 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