We investigate a problem arising in the computer-aided
design of cars, planes, ships, trains, and the like: Refine a
mesh of curved polygons, which approximates the surface of a
workpiece, into quadrilaterals so that the resulting
mesh is suitable for a numerical analysis.
This mesh refinement problem turns out to be strongly
NP-hard.
In commercial CAD systems, this problem is usually
solved in a greedy-like fashion. However, these
algorithms leave the user a lot of patchwork to do afterwards.
We introduce here a new global approach, which is based
on network flow techniques.
In a graph theoretical modeling of the problem we obtain
an undirected graph with upper and lower capacities on
the edges and some additional node constraints.
We reduce this problem to a sequence of bidirected flow
problems (or, equivalently, to b-matching problems).
For the first time, network flow techniques are applied to
a mesh refinement problem.
This approach avoids the local traps of greedy-like
approaches and yields solutions that require
significantly less additional patchwork.
Moreover, it permits local density control without any
additional overhead.
