A randomized parallel 3D convex hull algorithm for coarse grained multicomputers

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A randomized parallel 3D convex hull algorithm for coarse grained multicomputers

Full text

Pdf (714 KB)

Source

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

Santa Barbara, California, United States

Pages: 27 - 33

Year of Publication: 1995

ISBN:0-89791-717-0

Authors

Frank Dehne	School of Computer Science, Carleton University, Ottawa, Canada K1S
Xiaotie Deng	Dept. of Computer Science, York University, North York, Canada, M3J 1P3
Patrick Dymond	Dept. of Computer Science, York University, North York, Canada, M3J 1P3
Andreas Fabri	Dept. of Computer Science, Utrecht University, 3508, TB Utrecht, The Netherlands
Ashfaq A. Khokhar	School of EE and Dept. of Computer Sci., Purdue University, West Lafayette, IN

Sponsors

European Theoretical :
IEEE : Institute of Electrical and Electronics Engineers
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): 4, Downloads (12 Months): 30, Citation Count: 13

Additional Information:

references cited by index terms collaborative colleagues

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/215399.215410 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	A. and C. Yap. Parallel computational geometry, Algorithmica, Vol. 3, pages 293-327, 1988.
	2	A. Aggarwal , A. K. Chandra , M. Snir, On communication latency in PRAM computations, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.11-21, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72937]
	3	N.M. Amato, M. Goodrich, E. Ramos. Parallel Algorithms for high-dimensional convex hulls. Proc. 35th Annual IEEE Symposium on Foundations in Computer Science, pp. 683-694, 1994.
	4	Nancy M. Amato , Franco P. Preparata, An NC parallel 3D convex hull algorithm, Proceedings of the ninth annual symposium on Computational geometry, p.289-297, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.161152]
	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	M.J. Atallah and M.T. Goodrich. Parallel Mgorithms for some functions of two convex polygons. Algorithmica, Vol. 3, pages 535-548, 1988.
	7	N. Alon, and N. Meggido. Parallel Linear Programming in Fixed Dimension Almost Surely in Constant Time. FOCS90, pages 574-582.
	8	R.J. Anderson, and L. Snyder. A Comparison of Shared and Nonshared Memory Models of Computation. Proc. of IEEE, vol 79(4),pages 480-487.
	9	M. J. Atallah , J. J. Tsay, On the parallel decomposability of geometric problems, Proceedings of the fifth annual symposium on Computational geometry, p.104-113, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73845]
	10	Guy E. Blelloch , Charles E. Leiserson , Bruce M. Maggs , C. Greg Plaxton , Stephen J. Smith , Marco Zagha, A comparison of sorting algorithms for the connection machine CM-2, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.3-16, July 21-24, 1991, Hilton Head, South Carolina, United States [doi>10.1145/113379.113380]
	11	K.E. Batcher. Sorting networks and their applications. Proc. AFIPS Spring Joint Computer Con- }evence, pages 307-314, 1968.
	12	K.Q. Brown. Voronoi diagrams from convex hulls. Information Processing Letters, VoI. 9, 1979, pages 223-228.
	13	Anita Liu Chow, Parallel algorithms for geometric problems, 1980
	14	David Culler , Richard Karp , David Patterson , Abhijit Sahay , Klaus Erik Schauser , Eunice Santos , Ramesh Subramonian , Thorsten von Eicken, LogP: towards a realistic model of parallel computation, Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.1-12, May 19-22, 1993, San Diego, California, United States
	15	Kenneth L. Clarkson , Kurt Mehlhorn , Raimund Seidel, Four results on randomized incremental constructions, Computational Geometry: Theory and Applications, v.3 n.4, p.185-212, Sept. 1993 [doi>10.1016/0925-7721(93)90009-U]
	16	F. Dehne, A. Fabri, and C. Kenyon. Scalable and Architecture Independent Parallel Geometric Algorithms with High Probability Optimal Time. Proc. 6th IEEE Symposium on Parallel and Distributed Processing, pages 586-593, 1994.
	17	Frank Dehne , Andreas Fabri , Andrew Rau-Chaplin, Scalable parallel geometric algorithms for coarse grained multicomputers, Proceedings of the ninth annual symposium on Computational geometry, p.298-307, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.161154]
	18	X. Dent and N. Gu. Good Programming Style on Multiprocessors. Proceedings of IEEE Symposzum on Parallel and Distributed Processing, Dallas, October, 1994, pp.538-543,
	19	Xiaotie Deng, A Convex Hull Algorithm on Coarse-Grained Multiprocessors, Proceedings of the 5th International Symposium on Algorithms and Computation, p.634-64, August 25-27, 1994
	20	Xiaotie Deng , Patrick W. Dymond, Efficient routing and message bounds for optimal parallel algorithms, Proceedings of the 9th International Symposium on Parallel Processing, p.556, April 25-28, 1995
	21	D.P. Dobkin and D.G Kirkpatrick. Fast detection of polyhedral intersection. Theoretical Computer Science, Vol. 27, pages 241-253, 1983.
	22	Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
	23	P. B. Gibbons, A more practical PRAM model, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.158-168, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72953]
	24	Michael T. Goodrich, Planar separators and parallel polygon triangulation, Journal of Computer and System Sciences, v.51 n.3, p.374-389, Dec. 1995 [doi>10.1006/jcss.1995.1076]
	25	M.T. Goodrich, J.J. Tsay, D.E. Vengroff, and J.S. Vitter. External-memory computational geometry. Proc. 34th IEEE Symposium on Foundations of Computer Science, pages 714-723, 1993.
	26	Alexandros V. Gerbessiotis , Leslie G. Valiant, Direct Bulk-Synchronous Parallel Algorithms, Proceedings of the Third Scandinavian Workshop on Algorithm Theory, p.1-18, July 08-10, 1992
	27	Shay Halperin , Uri Zwick, An optimal randomized logarithmic time connectivity algorithm for the EREW PRAM (extended abstract), Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.1-10, June 27-29, 1994, Cape May, New Jersey, United States [doi>10.1145/181014.181017]
	28	S.E. Hambrusch and A.A. Khokhar. C3: An Architecture-independent Model for Coarse-Grained Parallel Machines. Proceedings of the 6-th IEEE Symposium on Parallel and Distributed Processing, 1994.
	29	F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
	30	Hui Li , Kenneth C. Sevcik, Parallel sorting by over partitioning, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.46-56, June 27-29, 1994, Cape May, New Jersey, United States [doi>10.1145/181014.192329]
	31	R.J. Lipton and R.E. Tarjan. Applications of a planar separator theorem. SIAM Journal of Computing, Vol. 9, No. 3, pages 615-627, 1980.
	32	Kurt Mehlhorn, Graph algorithms and NP-completeness, Springer-Verlag New York, Inc., New York, NY, 1984
	33	K. Mulmuley. Computational Geometry: An Introduction Through Randomized Algorithms. Prentice Hall, New York, NY, 1993.
	34	R. Miller , Q. F. Stout, Efficient Parallel Convex Hull Algorithms, IEEE Transactions on Computers, v.37 n.12, p.1605-1618, December 1988 [doi>10.1109/12.9737]
	35	Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
	36	Christos Papadimitriou , Mihalis Yannakakis, Towards an architecture-independent analysis of parallel algorithms, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.510-513, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62262]
	37	John H. Reif , Sandeep Sen, Erratum: optimal parallel randomized algorithms for three-dimensional convex hulls and related problems, SIAM Journal on Computing, v.23 n.2, p.447-448, April 1994 [doi>10.1137/0223030]
	38	Lawrence Snyder, Type architectures, shared memory, and the corollary of modest potential, Annual review of computer science vol. 1, 1986, Annual Reviews Inc., Palo Alto, CA, 1986
	39	Y. Shiloach and U. Vishkin. An o(logn) parallel connectivity algorithm. Journal of Algorithms, 3(1), pages 57-67, 1983.
	40	Leslie G. Valiant, A bridging model for parallel computation, Communications of the ACM, v.33 n.8, p.103-111, Aug. 1990 [doi>10.1145/79173.79181]
	41	L. G. Valiant, General purpose parallel architectures, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991

CITED BY 13

	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
	Pat Morin, Coarse grained parallel computing on heterogeneous systems, Proceedings of the 1998 ACM symposium on Applied Computing, p.628-634, February 27-March 01, 1998, Atlanta, Georgia, 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
	Edgar A. Ramos, Deterministic algorithms for 3-D diameter and some 2-D lower envelopes, Proceedings of the sixteenth annual symposium on Computational geometry, p.290-299, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong
	Nancy M. Amato , Michael T. Goodrich , Edgar A. Ramos, Computing the arrangement of curve segments: divide-and-conquer algorithms via sampling, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.705-706, January 09-11, 2000, San Francisco, California, United States
	Michael T. Goodrich, Communication-efficient parallel sorting (preliminary version), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.247-256, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	Frank Dehne , Wolfgang Dittrich , David Hutchinson, Efficient external memory algorithms by simulating coarse-grained parallel algorithms, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.106-115, June 23-25, 1997, Newport, Rhode Island, United States
	Laurence Boxer , Russ Miller, Coarse grained gather and scatter operations with applications, Journal of Parallel and Distributed Computing, v.64 n.11, p.1297-1310, November 2004
	E. L. G. Saukas , S. W. Song, Efficient selection algorithms on distributed memory computers, Proceedings of the 1998 ACM/IEEE conference on Supercomputing (CDROM), p.1-26, November 07-13, 1998, San Jose, CA
	Thierry Garcia , David Semé, A Coarse-Grained multicomputer algorithm for the detection of repetitions, Information Processing Letters, v.93 n.6, p.307-313, 31 March 2005
	Jeff Hightower , Marcia Talkmitt, 3D in the Pines and on the Plains, Proceedings of the 1998 ACM/IEEE conference on Supercomputing (CDROM), p.1-26, November 07-13, 1998, San Jose, CA
	Albert Chan , Frank Dehne , Prosenjit Bose , Markus Latzel, Coarse grained parallel algorithms for graph matching, Parallel Computing, v.34 n.1, p.47-62, January, 2008
	Charalampos Konstantopoulos , Basilis Mamalis , Grammati Pantziou , Damianos Gavalas, Efficient parallel Text Retrieval techniques on Bulk Synchronous Parallel (BSP)/Coarse Grained Multicomputers (CGM), The Journal of Supercomputing, v.48 n.3, p.286-318, June 2009