Improved Approximations for Minimum Cardinality Quadrangulations of Finite Element Meshes

dc.contributor.authorMüller-Hannemann, Matthias
dc.contributor.authorWeihe, Karsten
dc.description.abstractConformal mesh refinement has gained much attention as a necessary preprocessing step for the finite element method in the computer-aided design of machines, vehicles, and many other technical devices. For many applications, such as torsion problems and crash simulations, it is important to have mesh refinements into quadrilaterals. In this paper, we consider the problem of constructing a minimum-cardinality conformal mesh refinement into quadrilaterals. However, this problem is NP-hard, which motivates the search for good approximations. The previously best known performance guarantee has been achieved by a linear-time algorithm with a factor of 4. We give improved approximation algorithms. In particular, for meshes without so-called folding edges, we now present a 1.867-approximation algorithm. This algorithm requires O(n m log n) time, where n is the number of polygons and m the number of edges in the mesh. The asymptotic complexity of the latter algorithm is dominated by solving a T-join, or equivalently, a minimum-cost perfect b-matching problem in a certain variant of the dual graph of the mesh. If a mesh without foldings corresponds to a planar graph, the running time can be further reduced to O(n^{3/2} log n) by an application of the planar separator theorem.en
dc.subject.ddc510 Mathematiken
dc.subject.otherplanar graphen
dc.subject.otherconvex polygonen
dc.subject.othermesh refinementen
dc.subject.otherboundary edgeen
dc.subject.otherdual graphen
dc.titleImproved Approximations for Minimum Cardinality Quadrangulations of Finite Element Meshesen
dc.typeResearch Paperen
tub.affiliationFak. 2 Mathematik und Naturwissenschaften::Inst. Mathematikde
tub.affiliation.facultyFak. 2 Mathematik und Naturwissenschaftende
tub.affiliation.instituteInst. Mathematikde
tub.publisher.universityorinstitutionTechnische Universität Berlinen
tub.series.issuenumber1997, 559en
tub.series.namePreprint-Reihe des Instituts für Mathematik, Technische Universität Berlinen


Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
561.2 KB
Adobe Portable Document Format