Implementation and evaluation of an efficient parallel Delaunay triangulation algorithm

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Implementation and evaluation of an efficient parallel Delaunay triangulation algorithm

Full text

Pdf (1.33 MB)

Source

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

Newport, Rhode Island, United States

Pages: 239 - 248

Year of Publication: 1997

ISBN:0-89791-890-8

Author

Jonathan C. Hardwick

School of Computer Science, Carnegie Mellon University, Pittsburgh, Pennsylvania

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): 21, Downloads (12 Months): 90, Citation Count: 6

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/258492.258516 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. 6 Dtlnlaing, and C. Yap. Parallel computational geometry. Algorithmica, 3(3):293-327, 1988.
	2	Franz Aurenhammer, Voronoi diagrams—a survey of a fundamental geometric data structure, ACM Computing Surveys (CSUR), v.23 n.3, p.345-405, Sept. 1991 [doi>10.1145/116873.116880]
	3	Tom Axford, The divide-and-conquer paradigm as a basis for parallel language design, Advances in parallel algorithms, John Wiley & Sons, Inc., New York, NY, 1992
	4	C. Bradford Barber , David P. Dobkin , Hannu Huhdanpaa, The quickhull algorithm for convex hulls, ACM Transactions on Mathematical Software (TOMS), v.22 n.4, p.469-483, Dec. 1996 [doi>10.1145/235815.235821]
	5	Stephen T. Barnard, PMRSB: parallel multilevel recursive spectral bisection, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), p.27-es, December 04-08, 1995, San Diego, California, United States [doi>10.1145/224170.224227]
	6	Guy E. Blelloch, Vector models for data-parallel computing, MIT Press, Cambridge, MA, 1990
	7	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]
	8	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 [doi>10.1145/237218.237357]
	9	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
	10	L. Paul Chew, Nikos Chrisochoides, and Florian Sukup. Parallel constrained Delaunay meshing. In Proceedings of the joint ASME/ASCE/SES Summer Meeting Special Symposium on 7#,ends in Unstructured Mesh Generation, June 1997. To appear.
	11	P. Ciguoni, D. Laforenza, C. Montani, R. Perego, and R. Seopigno. Evaluation of parallelization strategies for an incremental Delaunay triangulator in E#. Technical Report C93-17, Consiglio Nazionale delle Ricerche, November 1993.
	12	P. Cignoni, C. Montani, R. Perego, and R. Scopigno. Parallel 3D Delaunay triangulation. In Proceedings of the Computer Graphics Forum (Eurographies '93), pages 129--142, 1993.
	13	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
	14	J.R. Davy and P.M. Dew. A note on improving the performance of Delaunay triangulation. In Proceedings of Computer Graphics international '89, pages 209--226, 1989.
	15	Yuemin Ding and Paul J. Densham. Dynamic and recursive parallel algorithms for constructing Delaunay triangulations. In Proceedings of the Sixth International Symposium on Spatial Data Handling, pages 682-696. Taylor & Francis, 1994.
	16	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]
	17	Steven Fortune. Voronoi diagrams and Delaunay triangulations. In Ding-Zhu Du and Frank Hwang, editors, Computing in Euclidean Geometry, pages 193- 233. World Scientific, 1992.
	18	Message Passing Interface Forum. MPI: A messagepassing interface standard. International Journal of Supereomputin9 Applications and High Performance Computing, 8(3/4), 1994.
	19	Sanjay Goil , Srinivas Aluru , Sanjay Ranka, Concatenated Parallelism: A Technique for Efficient Parallel Divide and Conquer, Proceedings of the 8th IEEE Symposium on Parallel and Distributed Processing (SPDP '96), p.488, October 23-26, 1996
	20	Sumanta Guha, An Optimal Mesh Computer Algorithm for Constralned Delaunay Triangulation, Proceedings of the 8th International Symposium on Parallel Processing, p.102-109, April 01, 1994
	21	Jonathan C. Hardwick. Porting a vector library: a comparison of MPI, Paris, CMMD and PVM. In Proceedin9s of the 1994 Scalable Parallel Libraries Conference, pages 68-77, October 1994.
	22	Jonathan C. Hardwiek. Aa efficient implementation of nested data parallelism for irregular divide-andconquer algorithms. In Proceedings of the First International Workshop on High-Level Programming Models and Supportive Environments, April 1996.
	23	Jonathan C. Hardwick. Implementation and evaluation of an efficient 2D parallel Delaunay triangulation algorithm. Technical Report CMU-CS-97-129, School of Computer Science, Carnegie Mellon University, April 1997.
	24	Jonathan C. Hardwick. Practical Parallel Divide.and- Conquer Algorithms. PhD thesis, School of Computer Science, Carnegie Mellon University, 1997. To appear.
	25	C. A. R. Hoare, Algorithm 63: partition, Communications of the ACM, v.4 n.7, p.321, July 1961 [doi>10.1145/366622.366642]
	26	C.A.R. Hoare. Quicksort. The Computer Journal, 5(1):10-15, 1962.
	27	J. Andrew Holey and Oscar H. Ibarra. Triangulation, Voronoi diagram, and convex hull in k-space on meshconnected arrays and hypercubes. In Proceedings of the 1991 International Conference on Parallel Processing, volume III, Algorithms & Applications. CRC Press, August 1991.
	28	Marshal L. Merriam. Parallel implementation of an algorithm for Delaunay triangulation. In Proceedings of Computational Fluid Dynamics, volume 2, pages 907- 912, September 1992.
	29	Mark H. Overmars and Jan van Leeuwen. Maintenance of configurations in the plane. Journal of Computer and System Sciences, 23:166-204, 1981.
	30	Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
	31	Jan F. Prins , Daniel W. Palmer, Transforming high-level data-parallel programs into vector operations, Proceedings of the fourth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.119-128, May 19-22, 1993, San Diego, California, United States
	32	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]
	33	Jonathan Richard Shewchuk, Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator, Selected papers from the Workshop on Applied Computational Geormetry, Towards Geometric Engineering, p.203-222, May 27-28, 1996
	34	Volker Strassen. Gaussian elimination is not optimal. Numerische Mathematik, 13(3):354-356, 1969.
	35	Peter Su, Efficient parallel algorithms for closet point problems, Dartmouth College, Hanover, NH, 1994
	36	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]
	37	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]
	38	N.A. Verhoeven, N.P. Weatherill, and K. Morgan. Dynamic load balancing in a 2D parallel Delaunay mesh generator, in Parallel Computational Fluid Dynamics, pages 641-648. Elsevier Science Publishers B.V. (North-Holland), June 1995.

CITED BY 6

	Marina L. Gavrilova, On a Nearest-Neighbor Problem Under Minkowski and Power Metrics for Large Data Sets, The Journal of Supercomputing, v.22 n.1, p.87-98, May 2002
	Marina L. Gavrilova, Empirical Studies of Optimization Techniques in the Event-Driven Simulation of Mechanically Alloyed Materials, The Journal of Supercomputing, v.28 n.2, p.165-176, May 2004
	Josef Kohout , Ivana Kolingerová, Parallel Delaunay triangulation based on circum-circle criterion, Proceedings of the 19th spring conference on Computer graphics, April 24-26, 2003, Budmerice, Slovakia
	Josef Kohout , Ivana Kolingerová , Jiří Žára, Parallel Delaunay triangulation in E² and E³ for computers with shared memory, Parallel Computing, v.31 n.5, p.491-522, May 2005
	Daniel K. Blandford , Guy E. Blelloch , Clemens Kadow, Engineering a compact parallel delaunay algorithm in 3D, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA
	Xiangyu Zhang , Armand Navabi , Suresh Jagannathan, Alchemist: A Transparent Dependence Distance Profiling Infrastructure, Proceedings of the 2009 International Symposium on Code Generation and Optimization, p.47-58, March 22-25, 2009