Finding connected components on a scan line array processor
Ronald I. Greenberg · 1995
Processor Thk paper provides a new approach to labeling the connected components of an n x n image on a scan line array processor (comprised of n processing elements).Variations of thk approach yield an algorithm guaranteed to complete in o(n lg n) time as well as algorithms likely to approach O(n) time for all or most images.The best previous solutions require using a more complicated architecture or require Q (n lg n) time.We also show that on a restricted version of the archkect ure, any algorithm requires Q(n lg n) time in the worst case.