PLANAR MESH REFINEMENT CANNOT BE BOTH LOCAL AND REGULAR

We show that two desirable properties for planar mesh refinement techn iques are incompatible. Mesh refinement is a common technique for adap tive error control in generating unstructured planar triangular meshes for piecewise polynomial representations of data. Local refinements a re modifications of the mesh that involve a fixed maximum amount of co mputation, independent of the number of triangles in the mesh. Regular meshes are meshes for which every interior vertex has degree 6. At le ast for some simple model meshing problems, optimal meshes are known t o be regular, hence it would be desirable to have a refinement techniq ue that, if applied to a regular mesh, produced a larger regular mesh. We call such a technique a regular refinement. In this paper, we prov e that no refinement technique can be both local and regular. Our resu lts also have implications for non-local refinement techniques such as Delaunay insertion or Rivara's refinement.