Complexity and Modeling Aspects of Mesh Refinement into Quadrilaterals

dc.contributor.authorMöhring, Rolf H.
dc.contributor.authorMüller-Hannemann, Matthias
dc.date.accessioned2021-12-17T10:08:06Z
dc.date.available2021-12-17T10:08:06Z
dc.date.issued1997
dc.description.abstractWe investigate the following mesh refinement problem: Given a mesh of polygons in three-dimensional space, find a decomposition into strictly convex quadrilaterals such that the resulting mesh is conforming and satisfies prescribed local density constraints. We show that this problem can be efficiently solved by a reduction to a bidirected flow problem, if the mesh does not contain folding edges, that is, edges incident to more than two polygons. In addition, optimization criteria such as density, angles and regularity can be handled to some extent by this approach, too. The general case with foldings, however, turns out to be strongly NP-hard. For special cases of the density constraints, the problem is feasible if and only if a certain system of linear equations over GF(2) has a solution. To enhance the mesh quality for meshes with foldings, we introduce a two-stage approach which first decomposes the whole mesh into components without foldings, and then uses minimum cost bidirected flows on the components in a second phase.en
dc.identifier.issn2197-8085
dc.identifier.urihttps://depositonce.tu-berlin.de/handle/11303/15649
dc.identifier.urihttp://dx.doi.org/10.14279/depositonce-14422
dc.language.isoenen
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subject.ddc510 Mathematiken
dc.subject.othermesh generationen
dc.subject.otherbidirected flowsen
dc.subject.otherNP-completenessen
dc.subject.othermesh decompositionen
dc.subject.otherComputer-Aided Designen
dc.titleComplexity and Modeling Aspects of Mesh Refinement into Quadrilateralsen
dc.typeResearch Paperen
dc.type.versionsubmittedVersionen
tub.accessrights.dnbfreeen
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, 554en
tub.series.namePreprint-Reihe des Instituts für Mathematik, Technische Universität Berlinen
Files
Original bundle
Now showing 1 - 1 of 1
Loading…
Thumbnail Image
Name:
Report-554-1997.pdf
Size:
395.89 KB
Format:
Adobe Portable Document Format
Description:
Collections