Cascading divide-and-conquer: a technique for designing parallel algorithms

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback
Take a look at the new version of this page: [ beta version ]. Tell us what you think.

Cascading divide-and-conquer: a technique for designing parallel algorithms

Source

SIAM Journal on Computing archive
Volume 18 , Issue 3 (June 1989) table of contents

Pages: 499 - 532

Year of Publication: 1989

ISSN:0097-5397

Authors

M. J. Atallah	Purdue Univ., West Lafayette, IN
R. Cole	New York Univ., New York, NY
M. T. Goodrich	Johns Hopkins Univ., Baltimore, MD

Publisher

Society for Industrial and Applied Mathematics Philadelphia, PA, USA

Bibliometrics

Downloads (6 Weeks): n/a, Downloads (12 Months): n/a, Citation Count: 33

Additional Information:

cited by index terms review collaborative colleagues

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

DOI Bookmark:	10.1137/0218035

CITED BY 33

	M. Atallah , P. Callahan , M. Goodrich, P-complete geometric problems, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.317-326, July 02-06, 1990, Island of Crete, Greece
	Michael T. Goodrich , S. Rao Kosaraju, Sorting on a parallel pointer machine with applications to set expression evaluation, Journal of the ACM (JACM), v.43 n.2, p.331-361, March 1996
	Mikhail J. Atallah , S. Rao Kosaraju, An efficient parallel algorithm for the row minima of a totally monotone matrix, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.394-403, January 28-30, 1991, San Francisco, California, United States
	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
	Michael T. Goodrich , Steven B. Shauck , Sumanta Guha, Parallel methods for visibility and shortest path problems in simple polygons (preliminary version), Proceedings of the sixth annual symposium on Computational geometry, p.73-82, June 07-09, 1990, Berkley, California, United States
	T. Tamassia , J. S. Vitter, Optimal cooperative search in fractional cascaded data structures, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.307-316, July 02-06, 1990, Island of Crete, Greece
	Pankaj K. Agarwal , Micha Sharir , Sivan Toledo, Applications of parametric searching in geometric optimization, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.72-82, September 1992, Orlando, Florida, United States
	Bernard Chazelle , Ding Liu, Lower bounds for intersection searching and fractional cascading in higher dimension, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.322-329, July 2001, Hersonissos, Greece
	Mikhail J. Atallah , Hubert Wagener , Danny Z. Chen, An optimal parallel algorithm for the visibility of a simple polygon from a point, Journal of the ACM (JACM), v.38 n.3, p.515-532, July 1991
	Yong K. Hwang , Narendra Ahuja, Gross motion planning—a survey, ACM Computing Surveys (CSUR), v.24 n.3, p.219-291, Sept. 1992
	Dharmavani Bhagavathi , Venkata V. Bokka , Himabindu Gurla , Stephan Olariu , James L. Schwing , Ivan Stojmenovic , Jingyuan Zhang, Time-Optimal Visibility-Related Algorithms on Meshes with Multiple Broadcasting, IEEE Transactions on Parallel and Distributed Systems, v.6 n.7, p.687-703, July 1995
	Mikhail J. Atallah , Michael T. Goodrich , S. Rao Kosaraju, Parallel algorithms for evaluating sequences of set-manipulation operations, Journal of the ACM (JACM), v.41 n.6, p.1049-1088, Nov. 1994
	John Hershberger, Optimal parallel algorithms for triangulated simple polygons, Proceedings of the eighth annual symposium on Computational geometry, p.33-42, June 10-12, 1992, Berlin, Germany
	Guy E. Blelloch , Margaret Reid-Miller, Pipelining with futures, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.249-259, June 23-25, 1997, Newport, Rhode Island, United States
	M. Atallah , D. Chen, Parallel rectilinear shortest paths with rectangular obstacles, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.270-279, July 02-06, 1990, Island of Crete, Greece
	Michael T. Goodrich, Constructing arrangements optimally in parallel (preliminary version), Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.169-179, July 21-24, 1991, Hilton Head, South Carolina, United States
	Sanguthevar Rajasekaran , Suneeta Ramaswami, Optimal parallel randomized algorithms for the Voronoi diagram of line segments in the plane and related problems, Proceedings of the tenth annual symposium on Computational geometry, p.57-66, June 06-08, 1994, Stony Brook, New York, United States
	Danny Z. Chen , Mikhail J. Atallah, Optimal Parallel Hypercube Algorithms for Polygon Problems, IEEE Transactions on Computers, v.44 n.7, p.914-922, July 1995
	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
	Danny Z. Chen, Efficient Geometric Algorithms on the EREW PRAM, IEEE Transactions on Parallel and Distributed Systems, v.6 n.1, p.41-47, January 1995
	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
	M. Goodrich , M. Ghouse , J. Bright, Generalized sweep methods for parallel computational geometry, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.280-289, July 02-06, 1990, Island of Crete, Greece
	Kenneth L. Clarkson , Richard Cole , Robert E. Tarjan, Randomized parallel algorithms for trapezoidal diagrams, Proceedings of the seventh annual symposium on Computational geometry, p.152-161, June 10-12, 1991, North Conway, New Hampshire, United States
	Danny Z. Chen, Efficient Parallel Binary Search on Sorted Arrays, with Applications, IEEE Transactions on Parallel and Distributed Systems, v.6 n.4, p.440-445, April 1995
	D. M. Nicol , A. G. Greenberg , B. D. Lubachevsky, Massively Parallel Algorithms for Trace-Driven Cache Simulations, IEEE Transactions on Parallel and Distributed Systems, v.5 n.8, p.849-859, August 1994
	Biing-Feng Wang, Finding r-Dominating Sets and p-Centers of Trees in Parallel, IEEE Transactions on Parallel and Distributed Systems, v.15 n.8, p.687-398, August 2004
	J. Ghosh , S. K. Das , A. John, Concurrent Processing of Linearly Ordered Data Structures on Hypercube Multicomputers, IEEE Transactions on Parallel and Distributed Systems, v.5 n.9, p.898-911, September 1994
	Yue-Li Wang , Hon-Chan Chen , Wei-Kai Liu, A Parallel Algorithm for Constructing a Labeled Tree, IEEE Transactions on Parallel and Distributed Systems, v.8 n.12, p.1236-1240, December 1997
	Amitava Datta , Anil Maheshwari , Jörg-Rüdiger Sack, Optimal parallel algorithms for direct dominance problems, Nordic Journal of Computing, v.3 n.1, p.72-88, Spring 1996
	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
	Bernard Chazelle , Ding Liu, Lower bounds for intersection searching and fractional cascading in higher dimension, Journal of Computer and System Sciences, v.68 n.2, p.269-284, March 2004
	Saverio Caminiti , Irene Finocchi , Rossella Petreschi, On coding labeled trees, Theoretical Computer Science, v.382 n.2, p.97-108, August, 2007
	Claudio Mirolo , Enrico Pagello, A New Cell-subdivision Approach to Plan Free Translations in Cluttered Environments, Journal of Intelligent and Robotic Systems, v.38 n.1, p.5-30, September 2003

INDEX TERMS

Primary Classification:
F. Theory of Computation
F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
F.2.2 Nonnumerical Algorithms and Problems
Subjects: Sorting and searching

General Terms:
Algorithms, Theory

REVIEW

"Thomas Rainer Michael Fischer : Reviewer"

The authors present new approaches to the design of parallel divide-and-conquer algorithms for problems in computational geometry. Their techniques apply whenever the merging step can be implemented by using only a restricted set of operations o more...

Collaborative Colleagues:

M. J. Atallah: colleagues

R. Cole: colleagues

M. T. Goodrich: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player