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.

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

Creative Commons License

Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 License.

Share

COinS