Developing a practical projection-based parallel Delaunay algorithm

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Developing a practical projection-based parallel Delaunay algorithm

Full text

Pdf (1.17 MB)

Source

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

Philadelphia, Pennsylvania, United States

Pages: 186 - 195

Year of Publication: 1996

ISBN:0-89791-804-5

Authors

Guy E. Blelloch	Computer Science Department, Carnegie Mellon University
Gary L. Miller	Computer Science Department, Carnegie Mellon University
Dafna Talmor	Computer Science Department, Carnegie Mellon University

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): 4, Downloads (12 Months): 28, 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/237218.237357 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. Parallel computational geometry. Algorithmica, 3(3):293-327, 1988.
	2	Marshall Bern, David Eppstein, and Frances ~ao. The expected extremes in a Delaunay triangulation. Inter. J. of Computational Geometry and Appl., 1(1):79-91, 1991.
	3	G. BlelIoch, G.L. Miller, and D. Talmor. Parallel Delaunay triangulation implementation. In MSI workshop on Computational geometry, Cornell, Oct 1994.
	4	Guy E. Blelloch , Jonathan C. Hardwick , Jay Sipelstein , Marco Zagha , Siddhartha Chatterjee, Implementation of a portable nested data-parallel language, Journal of Parallel and Distributed Computing, v.21 n.1, p.4-14, April 1994 [doi>10.1006/jpdc.1994.1038]
	5	Guy E. Blelloch , James J. Little, Parallel solutions to geometric problems in the scan model of computation, Journal of Computer and System Sciences, v.48 n.1, p.90-115, Feb. 1994 [doi>10.1016/S0022-0000(05)80023-6]
	6	Timothy M. Y. Chan , Jack Snoeyink , Chee-Keng Yap, Output-sensitive construction of polytopes in four dimensions and clipped Voronoi diagrams in three, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.282-291, January 22-24, 1995, San Francisco, California, United States
	7	A. Chow. Parallel Algorithms for Computational Geometry. PhD thesis, University of Illinois, 1980.
	8	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
	9	Frank Dehne , Xiaotie Deng , Patrick Dymond , Andreas Fabri , Ashfaq A. Khokhar, A randomized parallel 3D convex hull algorithm for coarse grained multicomputers, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.27-33, June 24-26, 1995, Santa Barbara, California, United States [doi>10.1145/215399.215410]
	10	R A Dwyer, A simple divide-and-conquer algorithm for computing Delaunay triangulations in O(n log log n) expected time, Proceedings of the second annual symposium on Computational geometry, p.276-284, June 02-04, 1986, Yorktown Heights, New York, United States [doi>10.1145/10515.10545]
	11	Herbert Edelsbrunner , Weiping Shi, An O(n log2h) time algorithm for the three-dimensional convex hull problem, SIAM Journal on Computing, v.20 n.2, p.259-269, April 1990 [doi>10.1137/0220016]
	12	Mujtaba R. Ghouse , Michael T. Goodrich, In-place techniques for parallel convex hull algorithms (preliminary version), Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.192-203, July 21-24, 1991, Hilton Head, South Carolina, United States [doi>10.1145/113379.113397]
	13	Leonidas Guibas , Jorge Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi, ACM Transactions on Graphics (TOG), v.4 n.2, p.74-123, April 1985 [doi>10.1145/282918.282923]
	14	David G Kirkpatrick , Raimund Seidel, The ultimate planar convex hull algorithm, SIAM Journal on Computing, v.15 n.1, p.287-299, Feb. 1986 [doi>10.1137/0215021]
	15	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]
	16	M. L. Merriam. Parallel implementation of an algorithra for delaunay triangulation. In First European Computational Fluid Dynamics Conference, pages 907-912, September 1992.
	17	Gary L. Miller , Dafna Talmor , Shang-Hua Teng , Noel Walkington, A Delaunay based numerical method for three dimensions: generation, formulation, and partition, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.683-692, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225286]
	18	Mark H. Overmars and Jan Van Leeuwen. Maintenance of configurations in the plane. Journal of Computer and System Sciences, 23:166-204, 1981.
	19	Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
	20	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]
	21	M.I. Shamos and D. Hoey. Closest-point problems. In 16~h Annual Symposium on Foundations of Computer Science, pages 151-162. IEEE, Oct 1975.
	22	Peter Su, Efficient parallel algorithms for closet point problems, Dartmouth College, Hanover, NH, 1994
	23	Peter Su , Robert L. Scot Drysdale, A comparison of sequential Delaunay triangulation algorithms, Proceedings of the eleventh annual symposium on Computational geometry, p.61-70, June 05-07, 1995, Vancouver, British Columbia, Canada [doi>10.1145/220279.220286]
	24	Y. A. Teng , F. Sullivan , I. Beichl , E. Puppo, A data-parallel algorithm for three-dimensional Delaunay triangulation and its implementation, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.112-121, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169667]
	25	A. Toomre. On the distribution of matter within highly flattened galaxies. The astrophysical journal, 138:385-392, 1963.
	26	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 [doi>10.1145/140901.141924]

CITED BY 8

	Guy E. Blelloch , John Greiner, A provable time and space efficient implementation of NESL, ACM SIGPLAN Notices, v.31 n.6, p.213-225, June 15, 1996
	Jonathan C. Hardwick, Implementation and evaluation of an efficient parallel Delaunay triangulation algorithm, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.239-248, June 23-25, 1997, Newport, Rhode Island, United States
	H.-W. Loidl , F. Rubio , N. Scaife , K. Hammond , S. Horiguchi , U. Klusik , R. Loogen , G. J. Michaelson , R. Peña , S. Priebe , Á J. Rebón , P. W. Trinder, Comparing Parallel Functional Languages: Programming and Performance, Higher-Order and Symbolic Computation, v.16 n.3, p.203-251, September 2003
	Andrey N. Chernikov , Nikos P. Chrisochoides, Practical and efficient point insertion scheduling method for parallel guaranteed quality delaunay refinement, Proceedings of the 18th annual international conference on Supercomputing, June 26-July 01, 2004, Malo, France
	Christos D. Antonopoulos , Xiaoning Ding , Andrey Chernikov , Filip Blagojevic , Dimitrios S. Nikolopoulos , Nikos Chrisochoides, Multigrain parallel Delaunay Mesh generation: challenges and opportunities for multithreaded architectures, Proceedings of the 19th annual international conference on Supercomputing, June 20-22, 2005, Cambridge, Massachusetts
	P. W. Trinder , H.-W. Loidl , R. F. Pointon, Parallel and Distributed Haskells, Journal of Functional Programming, v.12 n.5, p.469-510, July 2002
	Andrey N. Chernikov , Nikos P. Chrisochoides, Algorithm 872: Parallel 2D constrained Delaunay mesh generation, ACM Transactions on Mathematical Software (TOMS), v.34 n.1, p.1-20, January 2008
	Christos D. Antonopoulos , Filip Blagojevic , Andrey N. Chernikov , Nikos P. Chrisochoides , Dimitrios S. Nikolopoulos, A multigrain Delaunay mesh generation method for multicore SMT-based architectures, Journal of Parallel and Distributed Computing, v.69 n.7, p.589-600, July, 2009