DocumentCode :
2778480
Title :
Provably good mesh generation
Author :
Bern, Marshall ; Eppstein, David ; Gilbert, John
Author_Institution :
Xerox Palo Alto Res. Center, CA, USA
fYear :
1990
fDate :
22-24 Oct 1990
Firstpage :
231
Abstract :
Several versions of the problem of generating triangular meshes for finite-element methods are studied. It is shown how to triangulate a planar point set or a polygonally bounded domain with triangles of bounded aspect ratio, how to triangulate a planar point set with triangles having no obtuse angles, how to triangulate a point set in arbitrary dimension with simplices of bounded aspect ratio, and how to produce a linear-size Delaunay triangulation of a multidimensional point set by adding a linear number of extra points. All the triangulations have size within a constant factor of optimal and run in optimal time O(n log n+k) with input of size n and output of size k. No previous work on mesh generation simultaneously guarantees well-shaped elements and small total size
Keywords :
computational geometry; finite element analysis; acute angled triangles; bounded aspect ratio; finite-element methods; linear-size Delaunay triangulation; multidimensional point set; optimal size; planar point set; polygonally bounded domain; probably good mesh generation; simplices; triangular meshes; well-shaped elements; Computer science; Data analysis; Design automation; Finite element methods; Geometry; Mesh generation; Polynomials; Rendering (computer graphics); Solid modeling; Tree graphs;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Foundations of Computer Science, 1990. Proceedings., 31st Annual Symposium on
Conference_Location :
St. Louis, MO
Print_ISBN :
0-8186-2082-X
Type :
conf
DOI :
10.1109/FSCS.1990.89542
Filename :
89542
Link To Document :
بازگشت