Avoiding the global sort: a faster contour tree algorithm

DOI10.1007/S00454-017-9901-ZMaRDI QIDQ1688860zbMATH OpenOpenAlexFDO

Authors Benjamin Raichel, C. Seshadhri

Publication date 11 January 2018

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1411.2689, https://drops.dagstuhl.de/opus/volltexte/2016/5949/

zbMATH Keywords

computational geometrycomputational topologycontour trees

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: We revisit the classical problem of computing the emph{contour tree} of a scalar field $f:mathbbMomathbbR$, where $mathbbM$ is a triangulated simplicial mesh in $mathbb{R}^d$. The contour tree is a fundamental topological structure that tracks the evolution of level sets of $f$ and has numerous applications in data analysis and visualization. All existing algorithms begin with a global sort of at least all critical values of $f$, which can require (roughly) $Omega(nlogn)$ time. Existing lower bounds show that there are pathological instances where this sort is required. We present the first algorithm whose time complexity depends on the contour tree structure, and avoids the global sort for non-pathological inputs. If $C$ denotes the set of critical points in $mathbbM$, the running time is roughly $O(su{m}_{vinC}logel{l}_v)$, where $el{l}_v$ is the depth of $v$ in the contour tree. This matches all existing upper bounds, but is a significant improvement when the contour tree is short and fat. Specifically, our approach ensures that any comparison made is between nodes in the same descending path in the contour tree, allowing us to argue strong optimality properties of our algorithm. Our algorithm requires several novel ideas: partitioning $mathbbM$ in well-behaved portions, a local growing procedure to iteratively build contour trees, and the use of heavy path decompositions for the time complexity analysis.

Recommendations

• Avoiding the global sort: a faster contour tree algorithm
• Parallel computation of the topology of level sets
• Simple and optimal output-sensitive construction of contour trees using monotone paths
• Flexible isosurfaces: Simplifying and displaying scalar topology using the contour tree
• I/O-efficient contour tree simplification

Cites work

• scientific article; zbMATH DE number 4032498 (Why is no real title available?)
• scientific article; zbMATH DE number 1444011 (Why is no real title available?)
• A data structure for dynamic trees
• A data structure for manipulating priority queues
• A deterministic \(O(m \log m)\) time algorithm for the Reeb graph
• A randomized O ( m log m ) time algorithm for computing Reeb graphs of arbitrary simplicial complexes
• Computational topology. An introduction
• Computing contour trees in all dimensions
• Efficient algorithms for computing Reeb graphs
• Loops in Reeb graphs of 2-manifolds
• Simple and optimal output-sensitive construction of contour trees using monotone paths

Cited in

(6)

• Avoiding the global sort: a faster contour tree algorithm
• I/O-efficient contour tree simplification
• Parallel computation of the topology of level sets
• Correction to: ``Avoiding the global sort: a faster contour tree algorithm
• Maintaining contour trees of dynamic terrains
• Representing Interpolant Topology for Contour Tree Computation

This page was built for publication: Avoiding the global sort: a faster contour tree algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1688860)