Complexity and modeling aspects of mesh refinement into quadrilaterals

We investigate the following mesh refinement problem: Given a mesh of polyg ons in three-dimensional space, find a decomposition into strictly convex q uadrilaterals such that the resulting mesh is conforming and satisfies pres cribed local density constraints. The conformal mesh refinement problem is shown to be feasible if End only i f a certain system of linear equations over GF(2) has a solution. To improv e mesh quality with respect to optimization criteria such as density, angle s, and regularity, we introduce a reduction to a minimum cost bidirected fl ow problem. However, this model is only applicable if the mesh does not con tain branching edges, that is, edges incident to more than two polygons. Th e general case with branchings, however, turns out to be strongly NP-hard. To enhance the mesh quality for meshes with branchings, we introduce a two- stage approach which first decomposes the whole mesh into components withou t branchings, and then uses minimum cost bidirected flows on the components in a second phase.