Publikation: Improved Approximations for Minimum-Cardinality Quadrangulations of Finite-Element Meshes
Dateien
Datum
Autor:innen
Herausgeber:innen
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
URI (zitierfähiger Link)
Internationale Patentnummer
Link zur Lizenz
Angaben zur Forschungsförderung
Projekt
Open Access-Veröffentlichung
Core Facility der Universität Konstanz
Titel in einer weiteren Sprache
Publikationstyp
Publikationsstatus
Erschienen in
Zusammenfassung
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 2-approximation algorithm. This algorithm requires O(n2 log n) time, where n is the number of polygons in the mesh. The asymptotic complexity of the latter algorithm is dominated by solving a minimum-cost perfect b-matching problem in a certain variant of the dual graph of the mesh.
Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
Schlagwörter
Konferenz
Rezension
Zitieren
ISO 690
MÜLLER-HANNEMANN, Matthias, Karsten WEIHE, 1997. Improved Approximations for Minimum-Cardinality Quadrangulations of Finite-Element MeshesBibTex
@unpublished{MullerHannemann1997Impro-6363,
year={1997},
title={Improved Approximations for Minimum-Cardinality Quadrangulations of Finite-Element Meshes},
author={Müller-Hannemann, Matthias and Weihe, Karsten}
}RDF
<rdf:RDF
xmlns:dcterms="http://purl.org/dc/terms/"
xmlns:dc="http://purl.org/dc/elements/1.1/"
xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
xmlns:bibo="http://purl.org/ontology/bibo/"
xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#"
xmlns:foaf="http://xmlns.com/foaf/0.1/"
xmlns:void="http://rdfs.org/ns/void#"
xmlns:xsd="http://www.w3.org/2001/XMLSchema#" >
<rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/6363">
<dc:format>application/pdf</dc:format>
<dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
<dc:rights>terms-of-use</dc:rights>
<dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:12:13Z</dc:date>
<dc:creator>Müller-Hannemann, Matthias</dc:creator>
<dcterms:issued>1997</dcterms:issued>
<dc:contributor>Weihe, Karsten</dc:contributor>
<dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
<foaf:homepage rdf:resource="http://localhost:8080/"/>
<dcterms:title>Improved Approximations for Minimum-Cardinality Quadrangulations of Finite-Element Meshes</dcterms:title>
<dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/6363/1/preprint_030.pdf"/>
<dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:12:13Z</dcterms:available>
<void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
<dc:creator>Weihe, Karsten</dc:creator>
<dc:contributor>Müller-Hannemann, Matthias</dc:contributor>
<bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/6363"/>
<dcterms:abstract xml:lang="eng">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 2-approximation algorithm. This algorithm requires O(n2 log n) time, where n is the number of polygons in the mesh. The asymptotic complexity of the latter algorithm is dominated by solving a minimum-cost perfect b-matching problem in a certain variant of the dual graph of the mesh.</dcterms:abstract>
<dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/>
<dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/6363/1/preprint_030.pdf"/>
<dc:language>eng</dc:language>
</rdf:Description>
</rdf:RDF>
