Optimal point placement for mesh smoothing

We study the problem of moving a vertex in an unstructured mesh of triangul ar, quadrilateral, or tetrahedral elements to optimize the shapes of adjace nt elements. We show that many such problems can be solved in linear time u sing generalized linear programming. We also give efficient algorithms for some mesh smoothing problems that do not fit into the generalized linear pr ogramming paradigm. (C) 1999 Academic Press.