Document Type
Conference Proceeding
Publication Date
1995
Publication Title
Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures
Pages
195-202
Publisher Name
ACM
Abstract
This 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 this 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 Omega(n lg n) time. We also show that on a restricted version of the architecture, any algorithm requires Omega(n lg n) time in the worst case.
Recommended Citation
Proceedings of the Seventh Annual ACM Symposium on Parallel Algorithms and Architectures, Pages 195--202.
Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 License.
Copyright Statement
© ACM, 1995.
Presentation slides from Seventh Annual ACM Symposium on Parallel Algorithms and Architectures
Comments
Author Posting. © ACM, 1995. This article is posted here by permission of ACM for personal use, not for redistribution. The article was published in SPAA '95 Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, http://dx.doi.org/10.1145/215399.215444