TU Berlin

FG Kombinatorische Optimierung und Graphenalgorithmen1997

COGA 5-Wheel


zur Navigation

Preprints 1997

Complexity and Modeling Aspects of Mesh Refinement into Quadrilaterals
Zitatschlüssel Report-554-1997
Autor Möhring, Rolf H. and Müller-Hannemann, Matthias
Jahr 1997
Nummer 554
Notiz journal version appeared in Algorithmica (2000) 26, pp. 148-171, extended abstract appeared in Proceedings of the Eighth Annual International Symposium on Algorithms and Computation, ISAAC'97, Singapore, December 17-19, 1997, LNCS 1350, Springer-Verlag-Verlag, pp. 263-272.
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung 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.
Typ der Publikation Preprint
Link zur Publikation Download Bibtex Eintrag



Schnellnavigation zur Seite über Nummerneingabe