Abstract
There is a large and growing body of literature concerning the solutions of geometric problems on mesh-connected arrays of processors. Most of these algorithms are optimal (i.e., run in timeO(n 1/d) on ad-dimensionaln-processor array), and they all assume that the parallel machine is trying to solve a problem of sizen on ann-processor array. Here we investigate the situation where we have a mesh of sizep and we are interested in using it to solve a problem of sizen >p. The goal we seek is to achieve, when solving a problem of sizen >p, the same speed up as when solving a problem of sizep. We show that for many geometric problems, the same speedup can be achieved when solving a problem of sizen >p as when solving a problem of sizep.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
A. Aggarwal and M.-D. Huang. Network complexity of sorting and graph problems and simulating CRCW PRAMS by interconnection networks. InVLSI Algorithms and Architectures, 3rd Aegean Workshop on Computing, AWOC 88, pp. 339–350. Lecture Notes in Computer Science, Vol. 319, Springer-Verlag, Berlin, 1988.
A. Aggarwal and J. S. Vitter. The input/output complexity of sorting and related problems.Communications of the ACM, 31:1116–1127, September 1988.
M. J. Atallah, G. N. Frederickson, and S. R. Kosaraju. Sorting with efficient use of special-purpose sorters.Information Processing Letters, 27:13–15, 1988.
R. Beigel and J. Gill. Sortingn objects with ak-sorter.IEEE Transactions on Computers, 1990.
J. Bentley. Algorithms for Klee's rectangle problems. Unpublished notes, Computer Science Department, Carnegie-Mellon University, 1977.
J. Bentley. Multidimensional divide-and-conquer.Communications of the ACM, 23:214–229, April 1980.
B. Chazelle. Computational geometry on a systolic chip.IEEE Transactions on Computers, 33(9):774–785, September 1984.
R. Cole and M. T. Goodrich. Optimal parallel algorithms for polygon and pointset problems. InProceedings of the Fourth Annual Symposium on Computational Geometry, pp. 201–210, June 1988.
R. Cypher and J. L. C. Sanz. Optimal sorting on feasible parallel computers. InProceedings of the International Conference in Parallel Processing, 1988.
G. N. Frederickson and D. B. Johnson. The complexity of selection and ranking inX + Y and matrices with sorted columns.Journal of Computer and System Sciences, 24:197–208, 1982.
M. T. Goodrich. Efficient Parallel Techniques for Computational Geometry. Ph.D. thesis, Purdue University, 1987.
R. H. Giiting. Optimal divide-and-conquer to compute measure and contour for a set of iso-rectangles.Acta Informatica, 21:271–291, 1984.
J.-W. Hong and H. T. Kung. I/O complexity: the red-blue pebble game. InProceedings of the 13th Annual ACM Symposium on Theory of Computing, pp. 326–333, 1981
C. S. Jeong and D. T. Lee. Parallel geometric algorithms on a mesh connected computer.Algorithmica, 5:155–177, 1990.
H. T. Kung, F. Luccio, and F. P. Preparata. On finding the maxima of a set of vectors.Journal of the ACM, 22(4):469–476, 1975.
D. T. Lee, H. Chang, and C. K. Wong. An on-chip compare steer bubble sorter.IEEE Transactions on Computers, 30(6): 396–405, 1981.
D. T. Lee and F. P. Preparata. Computational geometry—a survey.IEEE Transactions on Computers, 33(12):872–1101, 1984.
R. Miller and Q. F. Stout. Mesh computer algorithms for computational geometry.IEEE Transactions on Computers, January 1989.
H. Mueller. Sorting numbers using limited systolic coprocessors.Information Processing Letters, 24:351–354, 1987.
M. Overmars and C. K. Yap. New upper bounds in Klee's measure problem. InProceedings of the 29th Annual IEEE Symposium on Foundations of Computer Science, pp. 550–556, 1988.
F. P. Preparata and M. I. Shamos.Computational Geometry. Springer-Verlag, New York, 1985.
Z.-C. Shih, G.-H. Chen, and R. C. T. Lee. Systolic algorithms to examine all pairs of elements,Communications of the ACM, 30(2): 161–167, February 1987.
J.-J. Tsay. Techniques for Solving Geometric Problems on Mesh-Connected Computers, Ph.D. thesis, Purdue University, 1990.
J.-J. Tsay and M. J. Atallah. Multisearch Techniques of Hierarchical DAGs on Mesh-Connected Computers, with Applications. Technical Report TR-1008, Department of Computer Science, Purdue University, 1990.
J. van Leeuwen and D. Wood. The measure problem for rectangular ranges ind-space.Journal of Algorithms, 10:51–56, 1980.
D. E. Willard and Y. C. Wee. Quasi-valid range querying and its implementations for nearest neighbor problem. InProceedings of the Fourth Annual Symposium on Computational Geometry, pp. 34–43, June 1988.
Author information
Authors and Affiliations
Additional information
Communicated by Leonidas Guibas.
The research of M. J. Atallah was supported by the Office of Naval Research under Contracts N00014-84-K-0502 and N00014-86-K-0689, the Air Force Office of Scientific Research under Grant AFOSR-90-0107, the National Science Foundation under Grant DCR-8451393, and the National Library of Medicine under Grant R01-LM05118. Jyh-Jong Tsay's research was partially supported by the Office of Naval Research under Contract N00014-84-K-0502, the Air Force Office of Scientific Research under Grant AFOSR-90-0107, and the National Science Foundation under Grant DCR-8451393.
Rights and permissions
About this article
Cite this article
Atallah, M.J., Tsay, J.J. On the parallel-decomposability of geometric problems. Algorithmica 8, 209–231 (1992). https://doi.org/10.1007/BF01758844
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01758844