Constructing arrangements optimally in parallel (preliminary version)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Constructing arrangements optimally in parallel (preliminary version)

Full text

Pdf (907 KB)

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: 169 - 179

Year of Publication: 1991

ISBN:0-89791-438-4

Author

Michael T. Goodrich

Department of Computer Science, The 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): 2, Downloads (12 Months): 13, Citation Count: 0

Additional Information:

references 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/113379.113395 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	P. K. Agarwal, A deterministic algorithm for partitioning arrangements of lines and its application, Proceedings of the fifth annual symposium on Computational geometry, p.11-22, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73835]
	2	A. ,Aggarwal, B. Chazelle, L. Guibas, C. O'Ddnlaing, and C. Yap, "Parallel Computational Geometry," Algorithmica, 3(3), 1988, 293-328.
	3	A. Aggarwal and J. Wein, Computational Geometry, M.I.T. Report MIT/LCS/RSS 3, 1988.
	4	R. Anderson , P. Beame , E. Brisson, Parallel algorithms for arrangements, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.298-306, July 02-06, 1990, Island of Crete, Greece [doi>10.1145/97444.97697]
	5	R. J. Anderson , G. L. Miller, Deterministic parallel list ranking, VLSI Algorithms and Architectures, Springer-Verlag, London, 1988
	6	M. J. Atallah , R. Cole , M. T. Goodrich, Cascading divide-and-conquer: a technique for designing parallel algorithms, SIAM Journal on Computing, v.18 n.3, p.499-532, June 1989 [doi>10.1137/0218035]
	7	J.L. Bentley and T. Ottmann, "Algorithms for Reporting and Counting Geometric Intersections," IEEE Trans. on Computers, C-28, 1979, 643-647.
	8	J.L. Bentley and D. Wood, "An Optimal Worst Case Algorithm for Reporting Intersections of Rectangles," IEEE Trans. on Computers, C-29(7), 1980, 571-576.
	9	Gianfranco Bilardi , Alexandru Nicolau, Adaptive Bitonic Sorting: An Optimal Parallel Algorithm for Shared Memory Machines, Cornell University, Ithaca, NY, 1986
	10	A. Borodin , J. E. Hopcroft, Routing, merging, and sorting on parallel models of computation, Journal of Computer and System Sciences, v.30 n.1, p.130-145, Feb. 1985 [doi>10.1016/0022-0000(85)90008-X]
	11	Richard P. Brent, The Parallel Evaluation of General Arithmetic Expressions, Journal of the ACM (JACM), v.21 n.2, p.201-206, April 1974 [doi>10.1145/321812.321815]
	12	Bernard Chaselle, Intersecting is easier than sorting, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.125-134, December 1984 [doi>10.1145/800057.808674]
	13	B. ChazeUe and H. Edelsbrunner, "An Optimal Algorithm for Intersecting Line Seg- " 29th FOCS, 1988 ments in the Plane, 590-600.
	14	B. Chazelle, L.J. Guibas, and D.T. Lee, "The Power of Geometric Duality," 24th FOCS, 1983, 217-225.
	15	Anita Liu Chow, Parallel algorithms for geometric problems, 1980
	16	K. Clarkson, "New Applications of Random Sampling in Computational Geometry," Discrete and Computational Geometry, Vol. 2, 1987, 195-222.
	17	Richard Cole, Parallel merge sort, SIAM Journal on Computing, v.17 n.4, p.770-785, August 1988 [doi>10.1137/0217049]
	18	R Cole , U Vishkin, Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.206-219, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12151]
	19	R. Cole and U. Vishkin, "Approximate and Exact Parallel Scheduling with Applications to List~ Tree and Graph Problems," Proc. 27th IEEE Syrup. on Foundations of Computer Science, 1986, 478-491.
	20	P.W. Dymon and S.A. Cook, "Hardware Complexity and Parallel Comp.," 21st IEEE Symp. on Found. of Comp. Sci., 1980, 360-372.
	21	Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
	22	H Edelsbrunner , L J Guibas, Topologically sweeping an arrangement, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.389-403, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12171]
	23	H. Edelsbrunner, J. O'Rourke, and R. Seidel, "Constructing Arrangements of Lines and Hyperplanes with Applications," 24ti~ FOCS~ 1983, 83-91.
	24	Michael Truman Goodrich , Mikhail J. Atallah, Efficient parallel techniques for computational geometry, 1987
	25	M. T. Goodrich, Intersecting line segments in parallel with an output-sensitive number of processors, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.127-137, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72950]
	26	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 [doi>10.1145/98524.98539]
	27	D. Haussler and E. Welzl, "e-Nets and Simplex Range Queries," Discrete and Computational Geometry, Vol. 2, 1987, 127-151.
	28	Torben Hagerup , H. Jung , E. Welzl, Efficient parallel computation of arrangements of hyperplanes in d dimensions, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.290-297, July 02-06, 1990, Island of Crete, Greece [doi>10.1145/97444.97696]
	29	Richard M. Karp, A Survey of Parallel Algorithms for Shared-Memory Machines, University of California at Berkeley, Berkeley, CA, 1988
	30	Kruskal, C.P., Rudolph, L., and Snir, M., "The Power of Parallel Prefix~" 1985 Int. Conf. on Parallel Processing, 180-185.
	31	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]
	32	D.T. Lee and F.P. Preparata, "Computational Geometry~A Survey," IEEE Trans. on Computers, Vol. C-33, No. 12, December 1984, pp. 872-1101.
	33	Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
	34	W.L. Ruzzo, "On Uniform Circuit Complexity," J. of Comp. and Sys. Sci., Vol. 22, No. 3, June 1981, 365-383.
	35	Y. Shiloach and U. Vishkin, "Finding the Maximum, Merging, and Sorting in a ParaUel Computation Model," journal of Algorithms, Vol. 2, 1981, pp. 88-102.
	36	James Christopher Wyllie, The complexity of parallel computations, 1979