# Improved Approximations for Minimum Cardinality Quadrangulations of Finite Element Meshes

 dc.contributor.author MÃ¼ller-Hannemann, Matthias dc.contributor.author Weihe, Karsten dc.date.accessioned 2021-12-17T10:07:53Z dc.date.available 2021-12-17T10:07:53Z dc.date.issued 1997 dc.description.abstract Conformal 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.identifier.issn 2197-8085 dc.identifier.uri https://depositonce.tu-berlin.de/handle/11303/15638 dc.identifier.uri http://dx.doi.org/10.14279/depositonce-14411 dc.language.iso en en dc.rights.uri http://rightsstatements.org/vocab/InC/1.0/ en dc.subject.ddc 510 Mathematik en dc.subject.other planar graph en dc.subject.other convex polygon en dc.subject.other mesh refinement en dc.subject.other boundary edge en dc.subject.other dual graph en dc.title Improved Approximations for Minimum Cardinality Quadrangulations of Finite Element Meshes en dc.type Research Paper en dc.type.version submittedVersion en tub.accessrights.dnb free en tub.affiliation Fak. 2 Mathematik und Naturwissenschaften::Inst. Mathematik de tub.affiliation.faculty Fak. 2 Mathematik und Naturwissenschaften de tub.affiliation.institute Inst. Mathematik de tub.publisher.universityorinstitution Technische UniversitÃ¤t Berlin en tub.series.issuenumber 1997, 559 en tub.series.name Preprint-Reihe des Instituts fÃ¼r Mathematik, Technische UniversitÃ¤t Berlin en

## Files

##### Original bundle
Now showing 1 - 1 of 1