MESH REFINEMENT VIA BIDIRECTED FLOWS - MODELING, COMPLEXITY, AND COMPUTATIONAL RESULTS

We investigate a problem arising in the computer-aided design of cars, planes, ships, trains, and other motor vehicles and machines: refine a mesh of curved polygons, which approximates the surface of a workpie ce, into quadrilaterals so that the resulting mesh is suitable for a n umerical analysis. This mesh refinement problem turns out to be strong ly NP-hard. In commercial CAD systems, this problem is usually solved using a greedy approach. However, these algorithms leave the user a lo t of patchwork to do afterwards. We introduce a new global approach, w hich is based on network now techniques. Abstracting from all geometri c and numerical aspects, 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, eq uivalently, to b-matching problems). For the first time, network flow techniques are applied to a mesh refinement problem. This approach avo ids the local traps of greedy approaches and yields solutions that req uire significantly less additional patchwork.