A randomized O ( m log m ) time algorithm for computing Reeb graphs of arbitrary simplicial complexes
William Harvey, Yusu Wang, Rephael Wenger · 2010
Given a continuous scalar field ƒ: X → where X is a topological space, a level set of ƒ is a set {x ∈ X : ƒ (x) = α} for some value α ∈ IR. The level sets of ƒ can be subdivided into connected components. As α changes continuously, the connected components in the level sets appear, disappear, split and merge. The Reeb graph of ƒ encodes these changes in connected components of level sets. It provides a simple yet meaningful abstraction of the input domain. As such, it has been used in a range of applications in fields such as graphics and scientific visualization.