journal version appeared in Algorithmica (2000) 26, pp. 148-171,
extended abstract
appeared in Proceedings of the Eighth Annual International
Symposium on Algorithms and
Computation, ISAAC'97, Singapore, December 17-19, 1997,
LNCS 1350, Springer-Verlag, pp. 263-272.
We investigate the following mesh refinement problem:
Given a mesh of polygons in three-dimensional space,
find a decomposition into strictly convex quadrilaterals
such that the resulting mesh is
conforming and satisfies prescribed local density constraints.
We show that this problem can be efficiently solved by a
reduction to a bidirected flow problem, if
the mesh does not contain folding edges, that is, edges
incident to more than two polygons. In addition,
optimization criteria such as density, angles and regularity
can be handled to some extent by this approach, too.
The general case with foldings, however,
turns out to be strongly NP-hard. For
special cases of the density constraints, the problem is
feasible if and only if a certain system of linear
equations over GF(2) has a solution.
To enhance the mesh quality for meshes with foldings, we
introduce a two-stage approach which first decomposes the
whole mesh into components without foldings, and then
uses minimum cost bidirected flows on the
components in a second phase.
