direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 520-1996

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

Mesh Refinement via Bidirected Flows: Modeling, Complexity, and Computational Results
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]
Title: Source

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe