Scalable parallel geometric algorithms for coarse grained multicomputers

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Scalable parallel geometric algorithms for coarse grained multicomputers

Full text

Pdf (909 KB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the ninth annual symposium on Computational geometry table of contents

San Diego, California, United States

Pages: 298 - 307

Year of Publication: 1993

ISBN:0-89791-582-8

Authors

Frank Dehne
Andreas Fabri
Andrew Rau-Chaplin

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 28, Citation Count: 21

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/160985.161154 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	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]
	2	K.E. Batcher. Sorting networks and their applications. Proc. A FIPS Spring Joint Computer Co~ference, pages 307-314, 1968.
	3	J. L. Bentley. Algorithms for Klee's rectangle problems. Carnegie-Mellon Unix,., Penn., Dept. of (~Jomp. Sci. Unpublished notes, 1977.
	4	Dimitri P. Bertsekas , John N. Tsitsiklis, Parallel and distributed computation: numerical methods, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
	5	R. Cypher , C. G. Plaxton, Deterministic sorting in nearly logarithmic time on the hypercube and related computers, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.193-203, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100240]
	6	Grand Challenges: High Performance Computing a'nd Communications. The FY 1992 U.S. Research and Development. Program. A Report by the Committee on Physical, Mathematical, and Engineering Sciences. Federal Council for Science, Engineering, and Technology. To Supplement the U.S. President's Fiscal Year 1992 Budget..
	7	R. I. Greenberg and C. E. Leiserson. Randomized Routing on Fat-trees. Advances in Computing Research, 5:345-374, 1989.
	8	F. Dehne and J.-R. Sack. Translation separability of sets of polygons. The Visual Computer .3: 227-235, 1987.
	9	F. Dehne and A. Fabri and A. Rau-Chaplin. Data structure decomposition./'or Coarse Grained Multicomputers. Manuscript.
	10	S Hart , M Sharir, Nonlinearity of Daveport:80Schinzel sequences and of generalized path compression schemes, Combinatorica, v.6 n.2, p.151-177, 1986 [doi>10.1007/BF02579170]
	11	J. Hershberger, Finding the upper envelope of n line segments in O(n log n) time, Information Processing Letters, v.33 n.4, p.169-174, December 1989 [doi>10.1016/0020-0190(89)90136-1]
	12	F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
	13	M. H. Overmars and J. van Leeuwen. Maintenance of configurations in the plane. J. Comput. Syst. Sci.. 23:166-2(.t4, 1981.
	14	Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
	15	John H. Reif , Leslie G. Valiant, A logarithmic time sort for linear size networks, Journal of the ACM (JACM), v.34 n.1, p.60-76, Jan. 1987 [doi>10.1145/7531.7532]
	16	J. van Leeuwen and D. Wood. The measure problem for rectangular ranges in d-space. J. Algorithms, 2:282-300, 1981.

CITED BY 21

	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
	Wolfgang Dittrich , David Hutchinson , Anil Maheshwari, Blocking in parallel multisearch problems (extended abstract), Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.98-107, June 28-July 02, 1998, Puerto Vallarta, Mexico
	Chun-Hsi Huang , Xin He, Finding a Hamiltonian paths in tournaments on clusters - a provably communication-efficient approach, Proceedings of the 2001 ACM symposium on Applied computing, p.549-553, March 2001, Las Vegas, Nevada, 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
	Micah Adler , Wolfgang Dittrich , Ben Juurlink , Mirosław Kutyłowski , Ingo Rieping, Communication-optimal parallel minimum spanning tree algorithms (extended abstract), Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.27-36, June 28-July 02, 1998, Puerto Vallarta, Mexico
	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
	Frank Dehne , Xiaotie Deng , Patrick Dymond , Andreas Fabri , Ashfaq A. Khokhar, A randomized parallel 3D convex hull algorithm for coarse grained multicomputers, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.27-33, June 24-26, 1995, Santa Barbara, California, United States
	Martin Dyer , Jonathan Nash , Peter Dew, An optimal randomized planar convex hull algorithm with good empirical performance, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.21-26, June 24-26, 1995, Santa Barbara, California, United States
	C. E. R. Alves , E. N. Cáceres , F. Dehne, Parallel dynamic programming for solving the string editing problem on a CGM/BSP, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada
	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
	John E. Savage, A model for multi-grained parallelism (extended abstract), Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.330-335, June 27-29, 1994, Cape May, New Jersey, United States
	Frank Dehne , Todd Eavis , Susanne Hambrusch , Andrew Rau-Chaplin, Parallelizing the Data Cube, Distributed and Parallel Databases, v.11 n.2, p.181-201, March 2002
	Douglas Gregor , Andrew Lumsdaine, Lifting sequential graph algorithms for distributed-memory parallel computation, ACM SIGPLAN Notices, v.40 n.10, October 2005
	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
	Haim Kaplan , Elad Verbin, Sorting signed permutations by reversals, revisited, Journal of Computer and System Sciences, v.70 n.3, p.321-341, May 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
	N. Gupta , S. Chopra, Output-sensitive algorithms for optimally constructing the upper envelope of straight line segments in parallel, Journal of Parallel and Distributed Computing, v.67 n.7, p.772-782, July, 2007
	Alexandros V. Gerbessiotis , Seung-Yeop Lee, Remote memory access: A case for portable, efficient and library independent parallel programming, Scientific Programming, v.12 n.3, p.169-183, August 2004
	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