Thumbnail
Access Restriction
Open

Author Bern, Marshall ♦ Eppstein, David ♦ Teng, Shang-Hua
Source CiteSeerX
Content type Text
Publisher Springer-Verlag
File Format PDF
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Extra Vertex ♦ Minimum Angle ♦ Parallel Construction ♦ Finite Element Method ♦ Input Domain ♦ Steiner Point ♦ Two-dimensional Mesh ♦ Mesh Generation ♦ Cient Pram Algorithm ♦ Unstructured Triangular Mesh ♦ Discretization Error ♦ Planar Straight-line Graph ♦ Quality Triangulation ♦ Versatile Type ♦ Typical Quality Guarantee ♦ Quadtree-based Finite Element Mesh ♦ Crucial Preprocessing Step ♦ Unbalanced Quadtrees ♦ Output Size
Description We describe e#cient PRAM algorithms for constructing unbalanced quadtrees, balanced quadtrees, and quadtree-based finite element meshes. Our algorithms take time O(log n) for point set input and O(log n log k) time for planar straight-line graphs, using O(n+k/ log n) processors, where n measures input size and k output size. 1 Introduction A crucial preprocessing step for the finite element method is mesh generation, and the most general and versatile type of two-dimensional mesh is an unstructured triangular mesh. Such a mesh is simply a triangulation of the input domain (e.g., a polygon), along with some extra vertices, called Steiner points. Not all triangulations, however, serve equally well; numerical and discretization error depend on the quality of the triangulation, meaning the shapes and sizes of triangles. A typical quality guarantee gives a lower bound on the minimum angle in the triangulation. Baker et al. [2] first proved the existence of quality triangulations for ...
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Learning Resource Type Article
Publisher Date 1993-01-01
Publisher Institution In Proc. 3rd Workshop Algorithms Data Struct