Edge Flips in Surface Meshes

Little theoretical work has been done on edge flips in surface meshes despite their popular usage in graphics and solid modeling to improve mesh equality. We propose the class of ((varepsilon ,alpha ))-meshes of a surface that satisfy several properties: the vertex set is an (varepsilon )-sample of the surface, the triangle angles are no smaller than a constant (alpha ), some triangle has a good normal, and the mesh is homeomorphic to the surface. We believe that many surface meshes encountered in practice are ((varepsilon ,alpha ))-meshes or close to being one. We prove that flipping the appropriate edges can smooth a dense ((varepsilon ,alpha ))-mesh by making the triangle normals better approximations of the surface normals and the dihedral angles closer to (pi ). Moreover, the edge flips can be performed in time linear in the number of vertices. This helps to explain the effectiveness of edge flips as observed in practice and in our experiments. A corollary of our techniques is that, in (mathbb {R}^2), every triangulation with a constant lower bound on the angles can be flipped in linear time to the Delaunay triangulation.