Publikation: Minimum Strictly Convex Quadrangulations of Convex Polygons
Lade...
Dateien
Datum
1996
Autor:innen
Müller-Hannemann, Matthias
Weihe, Karsten
Herausgeber:innen
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Konstanzer Schriften in Mathematik und Informatik
Auflagebezeichnung
URI (zitierfähiger Link)
Internationale Patentnummer
Link zur Lizenz
Angaben zur Forschungsförderung
Projekt
Open Access-Veröffentlichung
Open Access Green
Core Facility der Universität Konstanz
Titel in einer weiteren Sprache
Publikationstyp
Preprint
Publikationsstatus
Published
Erschienen in
Zusammenfassung
We present a linear-time algorithm that decomposes a convex polygon conformally into a minimum number of strictly convex quadrilaterals. Moreover, we characterize the polygons that can be decomposed without additional vertices inside the polygon, and we present a linear-time algorithm for such decompositions, too. As an application, we consider the problem of constructing a minimum conformal refinement of a mesh in the three-dimensional space, which approximates the surface of a workpiece. The latter problem has resulted from a cooperation with an engineering company that sells CAD packages. We have proved that this problem is strongly NP-hard, and we present a linear-time algorithm with a constant approximation ratio of 4.
Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
004 Informatik
Schlagwörter
Konferenz
Rezension
undefined / . - undefined, undefined
Zitieren
ISO 690
MÜLLER-HANNEMANN, Matthias, Karsten WEIHE, 1996. Minimum Strictly Convex Quadrangulations of Convex PolygonsBibTex
@unpublished{MullerHannemann1996Minim-6008,
year={1996},
title={Minimum Strictly Convex Quadrangulations of Convex Polygons},
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/6008">
<dcterms:issued>1996</dcterms:issued>
<dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/6008/1/preprint_013.pdf"/>
<dc:creator>Müller-Hannemann, Matthias</dc:creator>
<dc:creator>Weihe, Karsten</dc:creator>
<foaf:homepage rdf:resource="http://localhost:8080/"/>
<dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
<dc:contributor>Müller-Hannemann, Matthias</dc:contributor>
<dc:rights>terms-of-use</dc:rights>
<dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/>
<dcterms:title>Minimum Strictly Convex Quadrangulations of Convex Polygons</dcterms:title>
<dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/6008/1/preprint_013.pdf"/>
<dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:08:43Z</dc:date>
<dc:format>application/pdf</dc:format>
<dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:08:43Z</dcterms:available>
<dc:language>eng</dc:language>
<dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
<dcterms:abstract xml:lang="eng">We present a linear-time algorithm that decomposes a convex polygon conformally into a minimum number of strictly convex quadrilaterals. Moreover, we characterize the polygons that can be decomposed without additional vertices inside the polygon, and we present a linear-time algorithm for such decompositions, too. As an application, we consider the problem of constructing a minimum conformal refinement of a mesh in the three-dimensional space, which approximates the surface of a workpiece. The latter problem has resulted from a cooperation with an engineering company that sells CAD packages. We have proved that this problem is strongly NP-hard, and we present a linear-time algorithm with a constant approximation ratio of 4.</dcterms:abstract>
<void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
<dc:contributor>Weihe, Karsten</dc:contributor>
<bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/6008"/>
</rdf:Description>
</rdf:RDF>
