KOPS - The Institutional Repository of the University of Konstanz

Improved Approximations for Minimum-Cardinality Quadrangulations of Finite-Element Meshes

Improved Approximations for Minimum-Cardinality Quadrangulations of Finite-Element Meshes

Cite This

Files in this item

Checksum: MD5:0e7e14b87980faaf1d08decf9ff6be08

MÜLLER-HANNEMANN, Matthias, Karsten WEIHE, 1997. Improved Approximations for Minimum-Cardinality Quadrangulations of Finite-Element Meshes

@unpublished{MullerHannemann1997Impro-6363, title={Improved Approximations for Minimum-Cardinality Quadrangulations of Finite-Element Meshes}, year={1997}, author={Müller-Hannemann, Matthias and Weihe, Karsten} }

<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/rdf/resource/123456789/6363"> <dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/6363/1/preprint_030.pdf"/> <dc:contributor>Weihe, Karsten</dc:contributor> <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> <dc:rights>terms-of-use</dc:rights> <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> <dc:creator>Weihe, Karsten</dc:creator> <bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/6363"/> <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> <dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:12:13Z</dcterms:available> <dc:language>eng</dc:language> <dcterms:issued>1997</dcterms:issued> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:12:13Z</dc:date> <dc:format>application/pdf</dc:format> <dc:creator>Müller-Hannemann, Matthias</dc:creator> <foaf:homepage rdf:resource="http://localhost:8080/jspui"/> <dcterms:title>Improved Approximations for Minimum-Cardinality Quadrangulations of Finite-Element Meshes</dcterms:title> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dc:contributor>Müller-Hannemann, Matthias</dc:contributor> <dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/6363/1/preprint_030.pdf"/> </rdf:Description> </rdf:RDF>

Downloads since Oct 1, 2014 (Information about access statistics)

preprint_030.pdf 118

This item appears in the following Collection(s)

Search KOPS


Browse

My Account