Inhalt des Dokuments
Preprint 520-1996
Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)- Title
- Mesh Refinement via Bidirected Flows: Modeling, Complexity, and Computational Results
- Authors
- Publication
- appeared in the Journal of the ACM, vol. 44, no. 3 (May, 1997), pp. 395-426
- Classification
-
not available
- Keywords
-
not available
- Abstract
-
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.
- Source
- Download as [ps.Z]
Zusatzinformationen / Extras
Direktzugang
Schnellnavigation zur Seite über Nummerneingabe