An efficient expected time parallel algorithm for Voronoi construction

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

An efficient expected time parallel algorithm for Voronoi construction

Full text

Pdf (861 KB)

Source

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

San Diego, California, United States

Pages: 392 - 401

Year of Publication: 1992

ISBN:0-89791-483-X

Authors

B. C. Vemuri
R. Varadarajan
N. Mayya

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

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/140901.141924 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	A. Aggarwal, B. Chazelle, L. Guibas, C. O'Dunlaing and C. Yap {1988}, "Parallel Computational Geometry," in Algorithmica, No. 3, 293- 327.
	2	Selim G. Akl, The design and analysis of parallel algorithms, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
	3	Jon Louis Bentley , Bruce W. Weide , Andrew C. Yao, Optimal Expected-Time Algorithms for Closest Point Problems, ACM Transactions on Mathematical Software (TOMS), v.6 n.4, p.563-580, Dec. 1980 [doi>10.1145/355921.355927]
	4	:I.D. Boissonnat {1984}, "Representing 2D and 3D shapes with the Delaunay triangulation," in IEEE Seventh International Conference on Pattern Recognition, Montreal, Canada, pp. 745-748.
	5	K. Q. Brown {1979}, "Voronoi Diagrams from Convex Hulls," in Information Processing Letters, Vol 9, No. 5, 223-228.
	6	Richard Cole, Parallel merge sort, SIAM Journal on Computing, v.17 n.4, p.770-785, August 1988 [doi>10.1137/0217049]
	7	Richard Cole , Michael T. Goodrich , Colm Ó Dúnlaing, Merging free trees in parallel for efficient Voronoi diagram construction, Proceedings of the seventeenth international colloquium on Automata, languages and programming, p.432-445, July 1990, Warwick University, England
	8	Rex A. Dwyer, Higher-dimensional Voronoi diagrams in linear expected time, Discrete & Computational Geometry, v.6 n.4, p.343-367, 1991 [doi>10.1007/BF02574694]
	9	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]
	10	L. ,. Guibas, D. E. Knuth and M. Sharir {1990}, "Randomized Incremental Construction of Delaunay and Voronoi Diagrams," Tech. Rep., STAN- CS-90-1300, Stanford, CA.
	11	Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
	12	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 [doi>10.1145/73007.73045]
	13	B. C. Vemuri, R. Varadarajan and N. Mayya {1991}, "An O(log N) expected time parallel algorithm for Voronoi construction," Tech. Rep., Univ. of Florida, Gainesville, UF-CIS TR-91-25.

CITED BY 2

	Guy E. Blelloch , Gary L. Miller , Dafna Talmor, Developing a practical projection-based parallel Delaunay algorithm, Proceedings of the twelfth annual symposium on Computational geometry, p.186-195, May 24-26, 1996, Philadelphia, Pennsylvania, United States
	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