Penn Arts & Sciences Logo

Monday, February 6, 2006 - 4:30pm

Noel Walkington

Carnegie Mellon University

Location

University of Pennsylvania

307 Levine

Given a collection of points, edges, and faces, in a bounded two or three dimensional region, the meshing problem is to construct the a triangulation which (i) conforms to the given region, (ii) the triangles or tetrahedra have bounded aspect ratio, and (iii) is as coarse as possible. These requirements can lead to very complicated algorithms; so much so that it can be difficult to verify correctness. I will give an overview of the ideas and issues that arise when constructing algorithms to solve the meshing problem, and will indicate how the mesh generation problem touches on many areas of mathematics and computer science such as approximation/interpolation theory, computational geometry, sphere packing, graph theory, and algorithm design.