Intersecting line segments in parallel with an output-sensitive number of processors

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Intersecting line segments in parallel with an output-sensitive number of processors

Full text

Pdf (1.07 MB)

Source

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

Santa Fe, New Mexico, United States

Pages: 127 - 137

Year of Publication: 1989

ISBN:0-89791-323-X

Author

M. 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): 5, Downloads (12 Months): 25, Citation Count: 8

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/72935.72950 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	[1] A. Aggarwal, B. Chazelle, L. Guibas, C. Ó'Dúnlaing, and C. Yap, "Parallel Computational Geometry," Algorithmica, 3(3), 1988, 293-328.
	2	[2] M. J. Atallah, R. Cole, and M.T. Goodrich, "Cascading Divide-and-Conquer: A Technique for Designing Parallel Algorithms," 28th FOCS, 1987, 151-160.
	3	Mikhail J. Atallah , Michael T. Goodrich , S. Rao Kosaraju, Parallel Algorithms for Evaluating Sequences of Set-Manipulation Operations, Proceedings of the 3rd Aegean Workshop on Computing: VLSI Algorithms and Architectures, p.1-10, June 28-July 01, 1988
	4	[4] J. L. Bentley and T. Ottmann, "Algorithms for Reporting and Counting Geometric Intersections," IEEE Trans. on Computers, C-28, 1979, 643-647.
	5	[5] 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.
	6	[6] S. Bhatt and J. Y. Cai, "Take a Walk, Grow a Tree," 29th FOCS, 1988, 469-478.
	7	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]
	8	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]
	9	[9] B. Chazelle and H. Edelsbrunner, "An Optimal Algorithm for Intersecting Line Segments in the Plane," 29th FOCS, 1988, 590- 600.
	10	[10] B. Chazelle, L. J. Guibas, and D. T. Lee, "The Power of Geometric Duality," 24th FOCS, 1983, 217-225.
	11	Anita Liu Chow, Parallel algorithms for geometric problems, University of Illinois at Urbana-Champaign, Champaign, IL, 1980
	12	Richard Cole, Parallel merge sort, SIAM Journal on Computing, v.17 n.4, p.770-785, August 1988 [doi>10.1137/0217049]
	13	Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
	14	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]
	15	[15] H. Edelsbrunner, L. J. Guibas, J. Pach, R. Pollack, R. Seidel, and M. Sharir, "Arrangements of Curves in the Plane - Topology, Combinatorics, and Algorithms," UIUCDCS-R-88-1477, Dept. of Comp. Sci., Univ. of Illinois, 1988.
	16	[16] H. Edelsbrunner, J. O'Rourke, and R. Seidel, "Constructing Arrangements of Lines and Hyperplanes with Applications," 24th FOCS, 1983, 83-91.
	17	[17] S. K. Ghosh and D. M. Mount, "An Output Sensitive Algorithm for Computing Visibility Graphs," 28th FOCS, 1987, 11-19.
	18	[18] M. T. Goodrich, "A Polygonal Approach to Hidden-Line Elimination," 25th Allerton Conf., 1987, 849-858.
	19	Ralf Hartmut Güting, An optimal contour algorithm for iso-oriented rectangles, Journal of Algorithms, v.5 n.3, p.303-326, Sept. 1984 [doi>10.1016/0196-6774(84)90013-0]
	20	J. Hershberger, Finding the visibility graph of a simple polygon in time proportional to its size, Proceedings of the third annual symposium on Computational geometry, p.11-20, June 08-10, 1987, Waterloo, Ontario, Canada [doi>10.1145/41958.41960]
	21	[21] Kruskal, C. P., Rudolph, L., and Snir, M., "The Power of Parallel Prefix," 1985 Int. Conf. on Parallel Processing, 180-185.
	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	[23] W. Lipski, Jr. and F. P. Preparata, "Finding the Contour of a Union of Iso-Oriented Rectangles," J. Algorithms, 1, 1980, 235-246.
	24	[24] E. M. McCreight, "Priority Search Trees," SIAM J. on Comput., No. 14, 1985, 257-276.
	25	Otto Nurmi, A fast line-sweep algorithm for hidden line elimination, BIT, v.25 n.3, p.466-472, 1985 [doi>10.1007/BF01935366]
	26	Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
	27	J. H. Reif , S. Sen, An efficient output-sensitive hidden surface removal algorithm and its parallelization, Proceedings of the fourth annual symposium on Computational geometry, p.193-200, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73413]
	28	[28] A. Schmitt, "Time and Space Bounds for Hidden Line and Hidden Surface Algorithms," EUROGRAPHICS '81, 43-56.
	29	Derick Wood, The contour problem for rectilinear polygons, Information Processing Letters, v.19 n.5, p.229-236, Nov. 1984 [doi>10.1016/0020-0190(84)90058-9]
	30	James Christopher Wyllie, The complexity of parallel computations, Cornell University, Ithaca, NY, 1979

CITED BY 8

	Michael Karasick , David Strip, Intersecting solids on a massively parallel processor, ACM Transactions on Graphics (TOG), v.14 n.1, p.21-57, Jan. 1995
	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
	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
	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
	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
	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
	B. C. Vemuri , R. Varadarajan , N. Mayya, An efficient expected time parallel algorithm for Voronoi construction, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.392-401, June 29-July 01, 1992, San Diego, California, United States