Time complexity of practical parallel steiner point insertion algorithms

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback
Take a look at the new version of this page: [ beta version ]. Tell us what you think.

Time complexity of practical parallel steiner point insertion algorithms

Full text

Pdf (83 KB)

Source

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

Barcelona, Spain

SESSION: SPAA revue table of contents

Pages: 267 - 268

Year of Publication: 2004

ISBN:1-58113-840-7

Authors

Daniel A. Spielman	Massachusets Instute of Tech.
Shang-Hua Teng	Boston University
Alper Üngör	Duke University

Sponsors

ACM: Association for Computing Machinery
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): 6, Downloads (12 Months): 18, Citation Count: 3

Additional Information:

abstract 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/1007912.1007953 What is a DOI?

ABSTRACT

An effective method in practice to compute quality Delaunay triangulations is to apply parallel refinements that insert Steiner points whose prestars in the triangulation do not overlap. We show that these algorithms can be implemented in O(log m) time using m processors, where m is the output size. To our knowledge, this is the first such analysis.

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	Marshall Bern , David Eppstein , John Gilbert, Provably good mesh generation, Journal of Computer and System Sciences, v.48 n.3, p.384-409, June 1994 [doi>10.1016/S0022-0000(05)80059-5]
	2	M. Bern, D. Eppstein, and S.-H. Teng. Parallel construction of quadtrees and quality triangulations. Int. J. Comp. Geom. & Applications, 9(6):517--532, 1999.
	3	P. Chew. Guaranteed-quality triangular meshes. Tech. Rep. TR-89-983, Cornell University, Ithaca, 1989.
	4	Herbert Edelsbrunner , Damrong Guoy, Sink-insertion for mesh improvement, Proceedings of the seventeenth annual symposium on Computational geometry, p.115-123, June 2001, Medford, Massachusetts, United States [doi>10.1145/378583.378644]
	5	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 [doi>10.1145/513400.513418]
	6	T. Okusanya and J. Peraire. Parallel unstructured mesh generation. Proc.Int.Conf.Numer.Grid Gen., 719--729, 1996.
	7	Jim Ruppert, A new and simple algorithm for quality 2-dimensional mesh generation, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.83-92, January 25-27, 1993, Austin, Texas, United States
	8	D. A. Spielman, S.-H. Teng, and A. Üngör. Parallel Delaunay refinement: Algorithms and analyses. Proc. Int. Meshing Roundtable, 205--217, 2002.

CITED BY 3

	Sariel Har-Peled , Alper Üngör, A time-optimal delaunay refinement algorithm in two dimensions, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy
	Benoît Hudson , Gary L. Miller , Todd Phillips, Sparse parallel Delaunay mesh refinement, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA
	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