### Mesh refinement via bidirected flows: modeling, complexity, and computational resultsMesh refinement via bidirected flows: modeling, complexity, and computational results

Access Restriction
Subscribed

 Author Hhring, Rolf H. ♦ Mller-Hannemann, Matthias ♦ Wiehe, Karsten Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1997 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword NP-completeness ♦ b-matching problem ♦ Augmenting paths ♦ Bidirected flows ♦ Mesh generation ♦ Templates Abstract 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 $\textit{NP}-hardIn$ 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 flwo problems (or, equivalently, to $\textit{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. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1997-05-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 44 Issue Number 3 Page Count 32 Starting Page 395 Ending Page 426

#### Open content in new tab

Source: ACM Digital Library