Publikation: Map Simplification with Topology Constraints : Exactly and in Practice
Lade...
Dateien
Zu diesem Dokument gibt es keine Dateien.
Datum
2017
Autor:innen
Herausgeber:innen
ISSN der Zeitschrift
Electronic ISSN
ISBN
Bibliografische Daten
Verlag
Schriftenreihe
Auflagebezeichnung
DOI (zitierfähiger Link)
Internationale Patentnummer
Angaben zur Forschungsförderung
Projekt
Open Access-Veröffentlichung
Core Facility der Universität Konstanz
Titel in einer weiteren Sprache
Publikationstyp
Beitrag zu einem Konferenzband
Publikationsstatus
Published
Erschienen in
FEKETE, Sándor, ed., Vijaya RAMACHANDRAN, ed.. 19th Workshop on Algorithm Engineering and Experiments 2017 (ALENEX17) : Barcelona, Spain, 17-18 January 2017. Red Hook, NY: Curran Associates, 2017, pp. 185-196. ISBN 978-1-5108-3586-3. Available under: doi: 10.1137/1.9781611974768.15
Zusammenfassung
We consider the classical line simplification problem subject to a given error bound ∊ but with additional topology constraints as they arise for example in the map rendering domain. While theoretically inapproximability has been proven for these problem variants, we show that in practice one can solve medium sized instances optimally using an integer linear programming approach and larger instances using an heuristic approach which for medium-sized real-world instances yields close-to-optimal results. Our approaches are evaluated on data sets which are synthetically generated, stem from the OpenStreetMap project[1], and the recent GISCup competition [3].
Zusammenfassung in einer weiteren Sprache
Fachgebiet (DDC)
004 Informatik
Schlagwörter
Konferenz
ALENEX17, 17. Jan. 2017 - 18. Jan. 2017, Barcelona, Spain
Rezension
undefined / . - undefined, undefined
Zitieren
ISO 690
FUNKE, Stefan, Thomas MENDEL, Alexander MILLER, Sabine STORANDT, Maria WIEBE, 2017. Map Simplification with Topology Constraints : Exactly and in Practice. ALENEX17. Barcelona, Spain, 17. Jan. 2017 - 18. Jan. 2017. In: FEKETE, Sándor, ed., Vijaya RAMACHANDRAN, ed.. 19th Workshop on Algorithm Engineering and Experiments 2017 (ALENEX17) : Barcelona, Spain, 17-18 January 2017. Red Hook, NY: Curran Associates, 2017, pp. 185-196. ISBN 978-1-5108-3586-3. Available under: doi: 10.1137/1.9781611974768.15BibTex
@inproceedings{Funke2017Simpl-43425,
year={2017},
doi={10.1137/1.9781611974768.15},
title={Map Simplification with Topology Constraints : Exactly and in Practice},
isbn={978-1-5108-3586-3},
publisher={Curran Associates},
address={Red Hook, NY},
booktitle={19th Workshop on Algorithm Engineering and Experiments 2017 (ALENEX17) : Barcelona, Spain, 17-18 January 2017},
pages={185--196},
editor={Fekete, Sándor and Ramachandran, Vijaya},
author={Funke, Stefan and Mendel, Thomas and Miller, Alexander and Storandt, Sabine and Wiebe, Maria}
}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/43425">
<dc:contributor>Wiebe, Maria</dc:contributor>
<void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
<dc:creator>Mendel, Thomas</dc:creator>
<dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2018-10-02T14:08:34Z</dcterms:available>
<dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2018-10-02T14:08:34Z</dc:date>
<dc:contributor>Mendel, Thomas</dc:contributor>
<dc:contributor>Storandt, Sabine</dc:contributor>
<dc:contributor>Funke, Stefan</dc:contributor>
<dc:language>eng</dc:language>
<dcterms:issued>2017</dcterms:issued>
<dc:creator>Miller, Alexander</dc:creator>
<bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/43425"/>
<dcterms:title>Map Simplification with Topology Constraints : Exactly and in Practice</dcterms:title>
<dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
<dc:creator>Funke, Stefan</dc:creator>
<dc:creator>Storandt, Sabine</dc:creator>
<dcterms:abstract xml:lang="eng">We consider the classical line simplification problem subject to a given error bound ∊ but with additional topology constraints as they arise for example in the map rendering domain. While theoretically inapproximability has been proven for these problem variants, we show that in practice one can solve medium sized instances optimally using an integer linear programming approach and larger instances using an heuristic approach which for medium-sized real-world instances yields close-to-optimal results. Our approaches are evaluated on data sets which are synthetically generated, stem from the OpenStreetMap project[1], and the recent GISCup competition [3].</dcterms:abstract>
<foaf:homepage rdf:resource="http://localhost:8080/"/>
<dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
<dc:creator>Wiebe, Maria</dc:creator>
<dc:contributor>Miller, Alexander</dc:contributor>
</rdf:Description>
</rdf:RDF>Interner Vermerk
xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter
Prüfungsdatum der Dissertation
Finanzierungsart
Kommentar zur Publikation
Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Nein
