Map Simplification with Topology Constraints : Exactly and in Practice

Cite This

Files in this item

Files Size Format View

There are no files associated with this item.

FUNKE, Stefan, Thomas MENDEL, Alexander MILLER, Sabine STORANDT, Maria WIEBE, 2017. Map Simplification with Topology Constraints : Exactly and in Practice. ALENEX17. Barcelona, Spain, Jan 17, 2017 - Jan 18, 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, pp. 185-196. ISBN 978-1-5108-3586-3. Available under: doi: 10.1137/1.9781611974768.15

@inproceedings{Funke2017Simpl-43425, title={Map Simplification with Topology Constraints : Exactly and in Practice}, year={2017}, doi={10.1137/1.9781611974768.15}, isbn={978-1-5108-3586-3}, address={Red Hook, NY}, publisher={Curran Associates}, 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 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/43425"> <dc:creator>Funke, Stefan</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> <dc:creator>Storandt, Sabine</dc:creator> <dc:contributor>Funke, Stefan</dc:contributor> <dc:creator>Mendel, Thomas</dc:creator> <dc:contributor>Mendel, Thomas</dc:contributor> <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2018-10-02T14:08:34Z</dc:date> <dc:contributor>Wiebe, Maria</dc:contributor> <foaf:homepage rdf:resource="http://localhost:8080/jspui"/> <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/43425"/> <dc:creator>Miller, Alexander</dc:creator> <dc:contributor>Storandt, Sabine</dc:contributor> <dc:contributor>Miller, Alexander</dc:contributor> <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2018-10-02T14:08:34Z</dcterms:available> <dcterms:issued>2017</dcterms:issued> <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/> <dc:language>eng</dc:language> <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/rdf/resource/123456789/36"/> <dc:creator>Wiebe, Maria</dc:creator> <dcterms:title>Map Simplification with Topology Constraints : Exactly and in Practice</dcterms:title> </rdf:Description> </rdf:RDF>

This item appears in the following Collection(s)

Search KOPS


Browse

My Account