Quasilinear algorithm for the component tree
Laurent Najman, Michel Couprie · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · 2004
The level sets of a map are the sets of points with level above a given threshold. The connected components of the level sets, thanks to the inclusion relation, can be organized in a tree structure, that is called the component tree. This tree, under several variations, has been used in numerous applications. Various algorithms have been proposed in the literature for computing the component tree. The fastest ones have been proved to run in 0(nln(n)) complexity. In this paper, we propose a simple to implement quasi-linear algorithm for computing the component tree on symmetric graphs, based on Tarjan’s union-find principle.