Building the Component Tree in Quasi-Linear Time
IEEE Transactions on Image Processing2006Vol. 15(11), pp. 3531–3539
Citations Over TimeTop 1% of 2006 papers
Abstract
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 (considering the worst-case complexity) have been proven to run in O(n ln(n)). 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 procedure. We also propose an algorithm that computes the n most significant lobes of a map.
Related Papers
- → Incrementally fast updated frequent pattern trees☆(2007)183 cited
- → Maintenance of fast updated frequent pattern trees for record deletion(2009)33 cited
- → A Fast Updated Frequent Pattern Tree(2006)22 cited
- An Efficient FUFP-tree Maintenance Algorithm for Record Modification(2008)
- → Maintenance of Fast Updated Frequent Pattern Trees for Record Modification(2006)7 cited