Skip to main content
Article
Finding Connected Components on a Scan Line Array Processor
Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures
  • Ronald I. Greenberg, Loyola University Chicago
Document Type
Conference Proceeding
Publication Date
1-1-1995
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 Attribution-Noncommercial-No Derivative Works 3.0
Citation Information
Proceedings of the Seventh Annual ACM Symposium on Parallel Algorithms and Architectures, Pages 195--202.