Quadrangular refinements of convex polygons with an application to finite-element meshes

We present a linear-time algorithm that decomposes a convex polygon conform ally into a minimum number of strictly convex quadrilaterals. Moreover, we characterise the polygons that can be decomposed without additional vertice s inside the polygon, and we present a linear-time algorithm for such decom positions, too. As an application, we consider the problem of constructing a minimum conformal refinement of a mesh in the three-dimensional space, wh ich approximates the surface of a workpiece. We prove that this problem is strongly Np-hard, and we present a linear-time algorithm with a constant ap proximation ratio of four.