Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-14422
For citation please use:
Main Title: Complexity and Modeling Aspects of Mesh Refinement into Quadrilaterals
Author(s): Möhring, Rolf H.
Müller-Hannemann, Matthias
Type: Research Paper
URI: https://depositonce.tu-berlin.de/handle/11303/15649
http://dx.doi.org/10.14279/depositonce-14422
License: http://rightsstatements.org/vocab/InC/1.0/
Abstract: We 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.
Subject(s): mesh generation
bidirected flows
NP-completeness
mesh decomposition
Computer-Aided Design
Issue Date: 1997
Date Available: 17-Dec-2021
Language Code: en
DDC Class: 510 Mathematik
Series: Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin
Series Number: 1997, 554
ISSN: 2197-8085
TU Affiliation(s): Fak. 2 Mathematik und Naturwissenschaften » Inst. Mathematik
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:
Report-554-1997.pdf
Format: Adobe PDF | Size: 395.89 kB
DownloadShow Preview
Thumbnail

Item Export Bar

Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.