Abstract
Efficient implementation of global computations on a linear array of processors is complicated due to the small communication bandwidth and the large communication diameter of the array. This paper presents efficient parallel techniques for partitioning, movement, and reduction of data on linear arrays. Also, efficient data structures are used to enable fast sequential access of query points within each processor. This combination of serial and parallel techniques is used to derive an optimal parallel algorithm for computing the convex hull of each connected region in an n×n image. The algorithm takes O(n 2/p) time on a linear array with p processors, where 1≤p≤n/log n. This result is processor-time optimal since an optimal sequential algorithm takes O(n 2) to solve the problem. Thus, a linear array with n/log n processors can solve the above problem in O(n log n) time. In comparison, a two dimensional mesh-connected array of processors can solve this problem in O(n) time using n 2 processors. The processor-time product for the mesh is O(n 3), which is not optimal.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
A. Aggarwal, B. Chazelle, L. Guibas, C. O'Dunlaing, and C. Yap, “Parallel Computational Geometry”, Proc. 1985 Symp. on Foundations of Computer Science.
A. Aho, J. Hopcroft, J. Ullman, Design and Analysis of Computer Algorithms, Addison Wesley, 1974.
S. Akl, “Parallel Algorithms for Convex Hulls”, Dept. Computer Science, Queens University, Ontario, Canada, 1983.
M. J. Atallah and M. T. Goodrich, “Efficient Parallel Solutions to Some Geometric Problems”, J. of Parallel and Distributed Computing, 3, pp. 492–507, 1986.
H. M. Alnuweiri and V. K. Prasanna Kumar, “Optimal Geometric Algorithms on Fixed-Size Linear Arrays and Scan-Line Arrays”, Proc. Ann. Conf. on Computer Vision and Pattern Recognition, 1988.
H. M. Alnuweiri and V. K. Prasanna Kumar, “An Efficient VLSI Architecture with Applications to Geometric Problems”, Parallel Computing, 12, 1989, pp. 71–83.
G. Baudet and D. Stevenson, “Optimal Sorting Algorithms for Parallel Computers”, IEEE Trans.on Computers, C-27, January 1978.
K. A. Doshi and P. J. Varman, “Optimal Graph Algorithms on a Fixed-Size Linear Array”, IEEE Trans.on Computers, C-36, April 1987.
A. I. Fisher, “Scan Line Array Processors for Image Computations”, Int'l Symp. on Computer Architecture, 1986.
E. B. Hinkle, J. L. C. Sanz, A. K. Jain, and D. Petkovic, “P 3 E New Life for Projection-Based Image Processing”, J. of Parallel and Distributed Computing, 4, 1987, pp. 45–87.
C. E. Kim, “On The Cellular Convexity of Complexes”, IEEE Trans. on Pattern Analysis and Machine Intelligence, 1981, pp. 617–625.
H. T. Kung and J. A. Webb, “Mapping Image Processing Operations onto a Linear Systolic Machine”, Distributed Computing, 1, 1986.
R. Miller and Q. F. Stout, “Geometric Algorithms for Digitized Pictures on a Mesh-Connected Computer”, IEEE Trans. on Pattern Analysis and Machine Intelligence, March 1985.
F.P. Preparata and D.T. Lee, “Computational Geometry-A Survey”, IEEE Trans.on Computers, 33, pp. 1072–1100, 1984.
F. Preparata and M. I. Shamos, Computational Geometry: An Introduction. Springer-Verlag, New York, 1985.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1990 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Alnuweiri, H.M., Prasanna Kumar, V.K. (1990). Parallel convexity algorithms for digitized images on a linear array of processors. In: Asano, T., Ibaraki, T., Imai, H., Nishizeki, T. (eds) Algorithms. SIGAL 1990. Lecture Notes in Computer Science, vol 450. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-52921-7_89
Download citation
DOI: https://doi.org/10.1007/3-540-52921-7_89
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-52921-7
Online ISBN: 978-3-540-47177-6
eBook Packages: Springer Book Archive