Presenting a paper by William Harvey, Yusu Wang, and Rephael Wenger
Abstract: In this paper, we present the first sub-quadratic algorithm to compute the Reeb graph for a function on an arbitrary simplicial complex K. Our algorithm is randomized with an expected running time O(m log n), where m is the size of the 2-skeleton of K (i.e, total number of vertices, edges and triangles), and n is the number of vertices. This presents a significant improvement over the previous \Theta(mn) time complexity for arbitrary complex, matches (although in expectation only) the best known result for the special case of 2-manifolds, and is faster than current algorithms for any other special cases (e.g, 3-manifolds). Our algorithm is also very simple to implement. Preliminary experimental results show that it performs well in practice.