Access Restriction

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

   Open content in new tab
Source: ACM Digital Library