A platform for research: civil engineering, architecture and urbanism
A platform for research: civil engineering, architecture and urbanism
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 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 using a greedy approach. However, these algorithms leave the user a lot of patchwork to do afterwards. We introduce a new global approach, which is based on network flow techniques. Abstracting from all geometric 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, 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 approaches and yields solutions that require significantly less additional patchwork.
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 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 using a greedy approach. However, these algorithms leave the user a lot of patchwork to do afterwards. We introduce a new global approach, which is based on network flow techniques. Abstracting from all geometric 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, 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 approaches and yields solutions that require significantly less additional patchwork.
Mesh refinement via bidirected flows: modeling, complexity and computational results
Mohring, R.H. (author) / Muller-Hannemann, M. (author) / Weihe, K. (author)
Journal of the ACM ; 44 ; 395-426
1997
32 Seiten, 20 Quellen
Article (Journal)
English
Space-time mesh refinement method for simulating transient mixed flows
| Taylor & Francis Verlag | 2021