In-place techniques for parallel convex hull algorithms (preliminary version)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

In-place techniques for parallel convex hull algorithms (preliminary version)

Full text

Pdf (1.12 MB)

Source

ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the third annual ACM symposium on Parallel algorithms and architectures table of contents

Hilton Head, South Carolina, United States

Pages: 192 - 203

Year of Publication: 1991

ISBN:0-89791-438-4

Authors

Mujtaba R. Ghouse	Dept. of Computer Science, Johns Hopkins University, Baltimore, MD
Michael T. Goodrich	Dept. of Computer Science, Johns Hopkins University, Baltimore, MD

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 20, Citation Count: 7

Additional Information:

references cited by index terms collaborative colleagues peer to peer

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/113379.113397 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Aggarwal, A., Chazelle, B., Guibas, L., O'Dunlaing,C., and Yap, C., "Parallel Computational Geometry," Pvoc. 26th IEEE FOCS (1985), pp.46S-477.
	2	N. Alon and N. Megiddo, "Parallel Linear Programming in Fixed Dimension Almost Surely in Constant Time", Proc. 31st IEEE FOCS Symposium (1990), pp. 574-582.
	3	Andrew, A.M., "Another efficient algorithm for convex hulls in two dimensions," Info. Proc. Lett. 9, (1970) 0p.216-219.
	4	Avis, D., "On the complexity of finding the convex hull of a set of points," Report SOCS 79.2, (1979), School of Computer Science, McGill University,
	5	Mikhail J. Atallah , Michael T. Goodrich, Efficient parallel solutions to some geometric problems, Journal of Parallel and Distributed Computing, v.3 n.4, p.492-507, December 1, 1986 [doi>10.1016/0743-7315(86)90011-0]
	6	Atallah, M. J., and Goodrich, M. T., "Parallel Algorithms for Some Functions of Two Convex Polygons", Algorithmica 3 (1988), pp. 535-548.
	7	Jon Louis Bentley , Franco P. Preparata , Mark G. Faust, Approximation algorithms for convex hulls, Communications of the ACM, v.25 n.1, p.64-68, Jan. 1982 [doi>10.1145/358315.358392]
	8	O. Berkman , Z. Galil , B. Schieber , U. Vishkin, Highly parallelizable problems, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.309-319, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73036]
	9	Omer Berkman , Uzi Vishkin, Recursive star-tree parallel data-structure, University of Maryland at College Park, College Park, MD, 1990
	10	Donald R. Chand , Sham S. Kapur, An Algorithm for Convex Polytopes, Journal of the ACM (JACM), v.17 n.1, p.78-86, Jan. 1970 [doi>10.1145/321556.321564]
	11	Chernotr, H., "A measure of asymptotic efficiency for tests of a hypothesis based on the sum of the observations," Annals of Math. Star., 23 (1952), pp. 493-509.
	12	Anita Liu Chow, Parallel algorithms for geometric problems, 1980
	13	Cole, R., and Vishkin, U., "Approximate and exact parallel scheduling with applications to list, tree and graph problems," Proc. 27th IEEE FOCS, (1986) pp.478-491, pp.128-142.
	14	Richard Cole , Ofer Zajicek, An optimal parallel algorithm for building a data structure for planar point location, Journal of Parallel and Distributed Computing, v.8 n.3, p.280-285, Mar. 1990 [doi>10.1016/0743-7315(90)90103-V]
	15	Norm Dadoun , David G. Kirkpatrick, Parallel Construction of Subdivision Hierarchies, University of British Columbia, Vancouver, BC, Canada, 1987
	16	Herbert Edelsbrunner , Weiping Shi, An O(n log2h) time algorithm for the three-dimensional convex hull problem, SIAM Journal on Computing, v.20 n.2, p.259-269, April 1990 [doi>10.1137/0220016]
	17	David Eppstein , Zvi Galil, Parallel algorithmic techniques for combinatorial computation, Annual review of computer science: vol. 3, 1988, Annual Reviews Inc., Palo Alto, CA, 1988
	18	Graham, R.L., "An efficient algorithm for determining the convex hull of a planar set," Info. Proc. Left. 1, (1972) pp.132-133.
	19	Jarvis, R.A., "On the identification of the convex hull of a finite set of points in the plane," 1;nfo. Proc. Left. 2, (1973) pp. 18-21.
	20	Howard Karloff , Prabhakar Raghavan, Randomized algorithms and pseudorandom numbers, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.310-321, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62242]
	21	David G Kirkpatrick , Raimund Seidel, The ultimate planar convex hull algorithm, SIAM Journal on Computing, v.15 n.1, p.287-299, Feb. 1986 [doi>10.1137/0215021]
	22	Richard E. Ladner , Michael J. Fischer, Parallel Prefix Computation, Journal of the ACM (JACM), v.27 n.4, p.831-838, Oct. 1980 [doi>10.1145/322217.322232]
	23	Mathews, "Number Theory", Chelsea Publications, New York, (1961).
	24	Yossi Matias , Uzi Vishkin, Converting high probability into nearly-constant time—with applications to parallel hashing, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.307-316, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103453]
	25	Miller, R., and Stout, Q., F., "Parallel Algorithms for convex hulls," Proc. Comp. Vision and Pat. Recogn. (1988).
	26	Overmars, M.H., van Leeuwen, J., "Maintenance of configurations in the plane," J. Comput. and S~Ist. Sci. 23 (1981), pp.166-204.
	27	Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
	28	P. Ragde, The parallel simplicity of compaction and chaining, Proceedings of the seventeenth international colloquium on Automata, languages and programming, p.744-751, July 1990, Warwick University, England
	29	Raghavan, P., "Lecture Notes on Randomized Algorithms", unpublished manuscript.
	30	J. H. Reif , S. Sen, Polling: a new randomized sampling technique for computational geometry, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.394-404, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73045]
	31	Raimund Seidel, A Convex Hull Algorithm Optimal for Point Sets in Even Dimensions, University of British Columbia, Vancouver, BC, Canada, 1981
	32	R. Seidel, Output-size sensitive algorithms for constructive problems in computational geometry, Cornell University, Ithaca, NY, 1987
	33	Stout, Q. F., "Constant-Time Geometry on PRAMs", a~roc, of the 17th International Conference on Parallel Processing 1988, pp 104-107.
	34	Andrew Chi-Chih Yao, A Lower Bound to Finding Convex Hulls, Journal of the ACM (JACM), v.28 n.4, p.780-787, Oct. 1981 [doi>10.1145/322276.322289]

CITED BY 7

	Michael T. Goodrich , Yossi Matias , Uzi Vishkin, Optimal parallel approximation for prefix sums and integer sorting, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.241-250, January 23-25, 1994, Arlington, Virginia, United States
	Guy E. Blelloch , Gary L. Miller , Dafna Talmor, Developing a practical projection-based parallel Delaunay algorithm, Proceedings of the twelfth annual symposium on Computational geometry, p.186-195, May 24-26, 1996, Philadelphia, Pennsylvania, United States
	Neelima Gupta , Sandeep Sen, Faster output-sensitive parallel algorithms for 3D convex hulls and vector maxima, Journal of Parallel and Distributed Computing, v.63 n.4, p.488-500, April 2003
	Sandeep Sen, Parallel multidimensional search using approximation algorithms: with applications to linear-programming and related problems, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.251-260, June 24-26, 1996, Padua, Italy
	Neelima Gupta , Sandeep Sen, Faster output-sensitive parallel convex hulls for d≤3: optimal sublogarithmic algorithms for small outputs, Proceedings of the twelfth annual symposium on Computational geometry, p.176-185, May 24-26, 1996, Philadelphia, Pennsylvania, United States
	Edgar A. Ramos, Construction of 1-d lower envelopes and applications, Proceedings of the thirteenth annual symposium on Computational geometry, p.57-66, June 04-06, 1997, Nice, France
	Michael T. Goodrich, Randomized fully-scalable BSP techniques for multi-searching and convex hull construction, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.767-776, January 05-07, 1997, New Orleans, Louisiana, United States