Edge flips and deforming surface meshes

We study edge ips in a surface mesh and the maintenance of a deforming surface mesh. If the vertices are dense with respect to the local feature size and the triangles have angles at least a constant, we can ip edges in linear time such that all triangles have almost empty diametric balls. For a planar triangulation with a constant angle lower bound, we can ip it to the Delaunay triangulation in linear time. We combine edge ips and vertex insertions and deletions in an algorithm to maintain a deforming surface mesh, specified only by a dense sample of n points that move with the surface. Under a reasonable motion model, we can enforce bounded aspect ratios and a small approximation error throughout the deformation. The update takes O(n) time at each time step.Our surface mesh maintenance algorithm also gives a good performance in experiments.