Mesh Refinement via Bidirected Flows: Modeling, Complexity, and Computational Results

Rolf H. Möhring, Matthias Müller-Hannemann, and Karsten Weihe

appeared in the Journal of the ACM, vol. 44, no. 3 (May, 1997), pp. 395-426

not available

not available

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.

Download as [ps.Z]