Randomized parallel algorithms for trapezoidal diagrams

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Randomized parallel algorithms for trapezoidal diagrams

Full text

Pdf (1.03 MB)

Source

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

North Conway, New Hampshire, United States

Pages: 152 - 161

Year of Publication: 1991

ISBN:0-89791-426-0

Authors

Kenneth L. Clarkson	AT&T Bell Labs
Richard Cole	Courant Institute, New York University
Robert E. Tarjan	Princeton University and NEC Research Institute

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): 3, Downloads (12 Months): 16, Citation Count: 2

Additional Information:

references cited by index terms collaborative colleagues peer to peer

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/109648.109665 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.

	ACG89	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]
	AM88	R. J. Anderson , G. L. Miller, Deterministic parallel list ranking, VLSI Algorithms and Architectures, Springer-Verlag, London, 1988
	CE88	B. Chazelle and H. Edelsbrunner. An optimal algorithm for intersecting line segments in the plane. In Proceedings of the 29th Annual IEEE Symposium on Foundations of Computer Science, pages 590- 600, 1988.
	Cha90	B. Chazelle. Triangulating a simple polygon in linear time. In Proceedings of the 31th Annual IEEE Symposium on Foundations of Computer Science, pages 220- 230, 1990.
	CI84	B. Chazelle , J. Incerpi, Triangulation and shape-complexity, ACM Transactions on Graphics (TOG), v.3 n.2, p.135-152, April 1984 [doi>10.1145/357337.357340]
	Col88	Richard Cole, Parallel merge sort, SIAM Journal on Computing, v.17 n.4, p.770-785, August 1988 [doi>10.1137/0217049]
	CS89	K. L. Clarkson , P. W. Shor, Applications of random sampling in computational geometry, II, Discrete & Computational Geometry, v.4 n.5, p.387-421, 1989 [doi>10.1007/BF02187740]
	CTVW89	K. L. Clarkson , R. E. Tarjan , C. J. Van Wyk, A fast Las Vegas algorithm for triangulating a simple polygon, Discrete & Computational Geometry, v.4 n.5, p.423-432, 1989 [doi>10.1007/BF02187741]
	CV86	Richard Cole , Uzi Vishkin, Deterministic coin tossing with applications to optimal parallel list ranking, Information and Control, v.70 n.1, p.32-53, July 1986 [doi>10.1016/S0019-9958(86)80023-7]
	Ede87	Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
	FM84	A. Fournier , D. Y. Montuno, Triangulating Simple Polygons and Equivalent Problems, ACM Transactions on Graphics (TOG), v.3 n.2, p.153-174, April 1984 [doi>10.1145/357337.357341]
	Goo89a	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]
	Goo89b	M. T. Goodrich, Triangulating a polygon in parallel, Journal of Algorithms, v.10 n.3, p.327-351, September 1989 [doi>10.1016/0196-6774(89)90032-1]
	GSG89	M. T. Goodrich, S.B. Shauck, and S. Guha. Parallel methods for visibility and shortest path problems in simple polygons. Technical report, Computer Science Department, The Johns Hopkins University, 1989.
	HJW90	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]
	Mul88	K. Mulmuley. A fast planar point location algorithm' part I. In Proceedings of the ~9th Annual IEEE Symposium on Foundations of Computer Science, pages 580-589, 1988.
	RR88	S. Rajasekaran , J. H. Reif, Optimal and sublogarithmic time randomized parallel sorting algorithms, SIAM Journal on Computing, v.18 n.3, p.594-607, June 1989 [doi>10.1137/0218041]
	Sei	R. Seidel. A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons, manuscript.

CITED BY 2

	Michael T. Goodrich, Planar separators and parallel polygon triangulation (preliminary version), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.507-516, May 04-06, 1992, Victoria, British Columbia, Canada
	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