2 LINEAR-TIME UNION-FIND STRATEGIES FOR IMAGE-PROCESSING

We consider Union-Find as an appropriate data structure to obtain two linear time algorithms for the segmentation of images. The linearity i s obtained by restricting the order in which Union's are performed. Fo r one algorithm the complexity bound is proven by amortizing the Find operations. For the other we use periodic updates to keep the relevant part of our Union-Find-tree of constant height. Both algorithms are g eneralized and lead to new linear strategies for Union-Find that are n either covered by the algorithm of Gabow and Tarjan (1984) nor by the one of Dillencourt et al. (1992).