Optimal point placement for mesh smoothing

We study the problem of moving a vertex in a finite element mesh to optimize the shapes of adjacent triangles. We show that many such problems can be solved in linear time using generalized linear programming. We also give efficient algorithms for some mesh smoothing problems that do not fit into the generalized linear programming paradigm. 1 Introduction Unstructured mesh generation, a key step in the finite element method, can be divided into two stages. In point placement, the input domain is augmented by Steiner points and a preliminary mesh is formed, typically by Delaunay triangulation. In mesh improvement, local optimizations are performed, involving the movement of Steiner points and rearrangement of the triangulation. Computational geometry has made some inroads into point placement, and methods including Delaunay refinement, quadtrees, and circle packing are now known to generate meshes with guaranteed quality; for surveys of these results, see 8, 9. There has been less ...