Fast persistent homology computation for functions on ℝ
share
0-dimensional persistent homology is known, from a computational point of view, as the easy case. Indeed, given a list of n edges in non-decreasing order of filtration value, one only needs a union-find data structure to keep track of the connected components and we get the persistence diagram in time O(nα(n)). The running time is thus usually dominated by sorting the edges in Θ(nlog(n)). A little-known fact is that, in the particularly simple case of studying the sublevel sets of a piecewise-linear function on ℝ or 𝕊^1, persistence can actually be computed in linear time. This note presents a simple algorithm that achieves this complexity. An implementation will soon be available in Gudhi.
READ FULL TEXT