Title
Two Linear Time Union-Find Strategies for Image
Processing
Authors
-
Publication
Appeared in Theoretical Computer Science, vol. 154, no. 2, 1996.
Source
-
Classification
-
not available
Keywords
-
not available
-
-
We consider UF as an appropriate data structure to
obtain two linear time algorithms for the segmentation
of images. The linearity is obtained by restricting the
order in which Union's are performed. For 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 UF-tree of
constant height. Both algorithms are generalized and
lead to new linear strategies for UF that are neither
covered by the algorithm of Gabow and Tarjan nor by the
one of Dillencourt et al.
