Conformal mesh refinement has gained much attention as a
necessary preprocessing step for the finite element
method in the computer-aided design of machines,
vehicles, and many other technical devices.
For many applications, such as torsion problems and
crash simulations, it is important to have
mesh refinements into quadrilaterals.
In this paper, we consider the problem of constructing a
minimum-cardinality conformal mesh refinement into
quadrilaterals. However, this problem is NP-hard,
which motivates the search for good approximations.
The previously best known performance guarantee has
been achieved by a linear-time algorithm with a factor of 4.
We give improved approximation algorithms. In particular,
for meshes without so-called folding edges, we now present a
1.867-approximation algorithm. This algorithm
requires O(n m log n) time, where n is the
number of polygons and m the number of edges in the mesh.
The asymptotic complexity of the latter algorithm is
dominated by
solving a T-join, or equivalently, a minimum-cost
perfect b-matching problem in a certain variant of
the dual graph of the mesh.
If a mesh without foldings corresponds to a planar
graph, the running time can be further reduced to
O(n^{3/2} log n) by an application
of the planar separator theorem.
