Parallel processing for efficient subdivision search

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Parallel processing for efficient subdivision search

Full text

Pdf (939 KB)

Source

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

Waterloo, Ontario, Canada

Pages: 205 - 214

Year of Publication: 1987

ISBN:0-89791-231-4

Authors

N. Dadoun	Department of Computer Science, University of British Columbia, Vancouver, BC, CANADA V6T 1W5
D. G. Kirkpatrick	Department of Computer Science, University of British Columbia, Vancouver, BC, CANADA V6T 1W5

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

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

	ACGOYl	Aggtuwal. A.. Chazelle, B.. Guibas. L., O'Dunlaing, C., and Yap, C., "Parallel Computational Geometry (extended abstract)", Proc. of the 26th E?Z Symposium on Foundations of Computer Science (1985), pp. 468-477.
	ACGOY2	Aggarwal. A., Chazelle, B., Guibas, L.. O'Dunlaing, C., and Yap, C., "Parallel Computational Geometry ", To Appear in Algorithmica (1987).
	AG	M J Atallah , M T Goodrich, Efficient plane sweeping in parallel, Proceedings of the second annual symposium on Computational geometry, p.216-225, June 02-04, 1986, Yorktown Heights, New York, United States [doi>10.1145/10515.10539]
	CDH	Chrobak, M., Dii, K., and Hagerup, T., "Parallel S-Colouring of Planar Graphs", Preprint (1987).
	CV	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]
	DKl	David P. Dobkin , David G. Kirkpatrick, Fast Detection of Polyhedral Intersections, Proceedings of the 9th Colloquium on Automata, Languages and Programming, p.154-165, July 12-16, 1982
	DK2	Dobkin, D.P. and Kirkpatrick, D.G., "Fast Detection of Polyhedral Intersection", Theoretical Computer Science 27 (1983). pp. 241-253.
	DK3	Dobkin. D.P. and Kirkpatrick, D.G., "A Linear Time Algorithm for Determining the Separation of Convex Polyhedra", Journal of Algorithms 6.3 (1985). JJJ. 381-392.
	DK4	Dobkin, D.P. and Kirkpatrick, D.G., "Fast Algorithms for Preprocessed Polyhedral Intersection Detection", In Preparation.
	EKA	Ta. Asano, A new point-location algorithm and its practical efficiency: comparison with existing algorithms, ACM Transactions on Graphics (TOG), v.3 n.2, p.86-109, April 1984 [doi>10.1145/357337.357338]
	KW	Richard M. Karp , Avi Wigderson, A fast parallel algorithm for the maximal independent set problem, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.266-272, December 1984 [doi>10.1145/800057.808690]
	K	Kirkpatrick, D.G., "Optimal Search In Planar Subdivisions" SIAM Journal of Computing 12,l (1983). pp. 28-35.
	LM	Lipton, R.J., and Miller, R.E.. "A Batching Method for Coloring Planar Graphs", Information Processing Letters 7,4 (1978). pp. 185-188.
	L	M Luby, A simple parallel algorithm for the maximal independent set problem, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.1-10, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22146]
	MR	Miller, G.L. and Reif, J.H., "Parallel Tree Contraction and Its Application", Proc. of the 26th IEEE Symposium on Foundations of Computer Science (1985). pp- 478-489.
	PH	F. P. Preparata , S. J. Hong, Convex hulls of finite sets of points in two and three dimensions, Communications of the ACM, v.20 n.2, p.87-93, Feb. 1977 [doi>10.1145/359423.359430]
	SH	Shamos. M. I.. and Hoey. D., "Closest Point Problems" Proc. of the 16th IEEE Symposium on Foundations of Computer Science (1975), pp. 151-162.

CITED BY 9

	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
	Mikhail J. Atallah , Frank Dehne , Russ Miller , Andrew Rau-Chaplin , Jyh-Jong Tsay, Multisearch techniques for implementing data structures on a mesh-connected computer (preliminary version), Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.204-214, July 21-24, 1991, Hilton Head, South Carolina, United States
	R. Lin , S. Olariu, Optimal parallel coloring algorithms for a family of tree-representable graphs, Proceedings of the 19th annual conference on Computer Science, p.29-38, April 1991, San Antonio, Texas, United States
	J. H. Reif , S. Sen, Polling: a new randomized sampling technique for computational geometry, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.394-404, May 14-17, 1989, Seattle, Washington, United States
	D. E. Willard , Y. C. Wee, Quasi-Valid range querying and its implications for nearest neighbor problems, Proceedings of the fourth annual symposium on Computational geometry, p.34-43, June 06-08, 1988, Urbana-Champaign, Illinois, United States
	Sanjeev Saxena , P. C. Bhatt , V. C. Prasad, Efficient VLSI Parallel Algorithm for Delaunay Triangulation on Orthogonal Tree Network in Two and Three Dimensions, IEEE Transactions on Computers, v.39 n.3, p.400-404, March 1990
	Hossam ElGindy , Lochlan Wetherall, A Simple Voronoi Diagram Algorithm for a Reconfigurable Mesh, IEEE Transactions on Parallel and Distributed Systems, v.8 n.11, p.1133-1142, November 1997
	R. Tamassia , J. S. Vitter, Optimal parallel algorithms for transitive closure and point location in planar structures, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.399-408, June 18-21, 1989, Santa Fe, New Mexico, United States
	G. E. Shannon, Optimal on-line load balancing, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.235-245, June 18-21, 1989, Santa Fe, New Mexico, United States