A data-parallel algorithm for three-dimensional Delaunay triangulation and its implementation

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A data-parallel algorithm for three-dimensional Delaunay triangulation and its implementation

Full text

Pdf (945 KB)

Source

Conference on High Performance Networking and Computing archive
Proceedings of the 1993 ACM/IEEE conference on Supercomputing table of contents

Portland, Oregon, United States

Pages: 112 - 121

Year of Publication: 1993

ISBN:0-8186-4340-4

Authors

Y. A. Teng	Center for Automation Research, University of Maryland, College Park, MD
F. Sullivan	Supercomputing Research Center, Bowie, MD
I. Beichl	Computing and Applied Mathematics Laboratory, National Institute of Standard and Technology, Gaithersburg, MD
E. Puppo	Istituto per la Matematica Applicata, Consiglio Nazionale delle Ricerche, Via L.B. Alberti, 4-16132 Genova, Italy

Sponsor

SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 23, Citation Count: 4

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	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/169627.169667 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	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]
	2	F. Aurenhammer and H. Edelsbrunner. An optimal algorithm for constructing the weighted Voronoi diagram in the plane. Pattern Recognition, 17:251-257, 1984.
	3	I. Beichl and F. Sullivan. Fast triangulation via empty spheres, manuscript, 1992.
	4	J. Bernal. On the expected complexity of the 3- dimensional Voronoi diagram. Technical Report NISTIR-4321, National Institute of Standards and Technology, 1990.
	5	Guy E. Blelloch, Vector models for data-parallel computing, MIT Press, Cambridge, MA, 1990
	6	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]
	7	Herbert Edelsbrunner , Ernst Peter Mücke, Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms, ACM Transactions on Graphics (TOG), v.9 n.1, p.66-104, Jan. 1990 [doi>10.1145/77635.77639]
	8	H. Edelsbrunner and E. Miicke. Three dimensional alpha shapes. Technical Report UIUCDCS-R-92-1734, Dept. of Computer Science, University of Illinois at Urbana-Champion, 1992.
	9	H. Edelsbrunner , N. R. Shah, Incremental topological flipping works for regular triangulations, Proceedings of the eighth annual symposium on Computational geometry, p.43-52, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142688]
	10	W. Daniel Hillis , Guy L. Steele, Jr., Data parallel algorithms, Communications of the ACM, v.29 n.12, p.1170-1183, Dec. 1986 [doi>10.1145/7902.7903]
	11	H. Inagaki, K. Sugihara, and N. Sugie. Numerically robust incremental algorithm for constructing threedimensional Voronoi diagrams. In Proc. Fourth Canadian Conference on Computational Geometry, pages 334-339, 1992.
	12	E. Puppo et al. Parallel terrain triangulation. In Proc. Filth International Symposium on Spatial Data Handling, pages 632-641, 1992.
	13	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 [doi>10.1109/12.48871]
	14	G. Stewart. httroductiot~ to Ma~riav Computations. Academic Press, New York, 1973.

CITED BY 4

	Démian Nave , Nikos Chrisochoides , L. Paul Chew, Guaranteed: quality parallel delaunay refinement for restricted polyhedral domains, Proceedings of the eighteenth annual symposium on Computational geometry, p.135-144, June 05-07, 2002, Barcelona, Spain
	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
	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
	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