×
Akl, S. G.

Optimal parallel algorithms for computing convex hulls and for sorting. (English) Zbl 0526.68062

Computing 33, 1-11 (1984).
Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page
scan of Zbl 0526.68062

Cited in 16 Documents

MSC:

68P10 Searching and sorting
68Q25 Analysis of algorithms and problem complexity
52A10 Convex sets in \(2\) dimensions (including convex curves)
68R99 Discrete mathematics in relation to computer science
52-04 Software, source code, etc. for problems pertaining to convex and discrete geometry

Keywords:

parallel algorithm; convex hull; parallel sorting algorithm; median; selection
Cite Review PDF
Full Text: DOI

References:

[1] Graham, R. L.: An efficient algorithm for determining the convex hull of a finite planar set. Information Processing Letters1, 132–133 (1972). · Zbl 0236.68013 · doi:10.1016/0020-0190(72)90045-2
[2] Shamos, M. I., Hoey, D.: Closest-point problems. Proceedings of the 16th Annual IEEE Symposium on Foundations of Computer Science, New York, October 1975, pp. 151–162.
[3] Preparata, F. P., Hong, S. J.: Convex hulls of finite sets of points in two and three dimensions. Communications of the ACM20, 87–93 (1977). · Zbl 0342.68030 · doi:10.1145/359423.359430
[4] Akl, S. G., Toussaint, G. T.: A fast convex hull algorithm Information Processing Letters7, 219–222 (1978). · Zbl 0392.52003 · doi:10.1016/0020-0190(78)90003-0
[5] Yao, A. C.-C.: A lower bound to finding convex hulls. Journal of the ACM28, 780–787 (1981). · Zbl 0468.68080 · doi:10.1145/322276.322289
[6] Kirkpatrick, D. G. Seidel, R.: The ultimate planar convex hull algorithm? Proceedings of the 20th Allerton Conference on Communication, Control and Computing, Monticello, Illinois, October 1982. · Zbl 0589.68035
[7] Chow, A. L.: A parallel algorithm for determining convex hulls of sets of points in two dimensions. Proceedings of the 19th Allerton Conference on Communication, Control and Computing, Monticello, Illinois, September 30 – October 2, 1981, pp. 214–223.
[8] Nath, D., Maheshwari, S. N., Bhatt, P. C. P.: Parallel algorithms for the convex hull problem in two dimensions. Technical Report EE 8005, Department of Electrical Engineering, Indian Institute of Technology, New Delhi, India, October 1980.
[9] Akl, S. G.: A constant-time parallel algorithm for computing convex hulls. BIT22, 130–134 (1982). · Zbl 0482.68065 · doi:10.1007/BF01944471
[10] Chandra, A. K., Stockmeyer, L. J., Vishkin, U.: A complexity theory for unbounded fan-in parallelism. Proceedings of the 23rd Symposium on Foundations of Computer Science, Chicago, Illinois, November 1982, pp. 1–13.
[11] Ralston, A., ed.: Encyclopedia of computer science and engineering, 2nd ed., p. 954; p. 1456. Toronto: Van Nostrand Reinhold 1983.
[12] Flynn, M. J.: Very high-speed computing systems. Proceedings of the IEEE54, 1901–1909 (1966). · doi:10.1109/PROC.1966.5273
[13] Akl, S. G.: An optimal algorithm for parallel selection. Technical Report No. 83-146, Department of Computing and Information Science, Queen’s University, Kingston, Ontario, Canada, April 1983. Information Processing Letters (to appear).
[14] Shamos, M. I.: Geometric complexity. Proceedings of the 7th Annual ACM Symposium on Theory of Computing, Albuquerque, New Mexico, May 1975, pp. 224–233. · Zbl 0357.68046
[15] Knuth, D. E.: The art of computer programming, Vol. 3: Sorting and Searching. Don Mills, Ontario: Addison-Wesley 1973. · Zbl 0191.17903
[16] Stone, H. S.: Parallel processing with the perfect shuffle. IEEE Transactions on ComputersC-20, 153–161 (1971). · Zbl 0214.42703 · doi:10.1109/T-C.1971.223205
[17] Preparata, F. P.: New parallel sorting schemes. IEEE Transactions on ComputersC-27, 669–673 (1978). · Zbl 0379.68025 · doi:10.1109/TC.1978.1675167
[18] Borodin, A., Hopcroft, J. E.: Routing, merging and sorting on parallel models of computation. Proceedings of the 14th Annual ACM Symposium on Theory of Computing, San Francisco, California, May 5–7, 1982, pp. 338–344. · Zbl 0603.68065
[19] Batcher, K. E.: Sorting networks and their applications. Proceedings of the AFIPS 1968 SJCC, Vol. 32, pp. 307–317. Montvale, N.J.: AFIPS Press 1968.
[20] Nassimi, D., Sahni, S.: Parallel permutation and sorting algorithms and a new generalized connection network. Journal of the ACM29, 642–667 (1982). · Zbl 0488.68045 · doi:10.1145/322326.322329
[21] Todd, S.: Algorithms and hardware for a merge sort using multiple processors. IBM Journal of Research and Development22, 509–517 (1978). · Zbl 0382.68057 · doi:10.1147/rd.225.0509
[22] Shiloach, Y., Vishkin, U.: Finding the maximum, merging and sorting in a parallel computation model. Technical Report Nr. 173, Department of Computer Science, Israel Institute of Technology, Haifa, Israel, March 1980. · Zbl 0456.68062
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.