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, and the recent GISCup competition.
%0 Conference Paper
%1 conf/alenex/FunkeMMSW17
%A Funke, Stefan
%A Mendel, Thomas
%A Miller, Alexander
%A Storandt, Sabine
%A Wiebe, Maria
%B Proceedings of the Meeting on Algorithm Engineering and Experiments (ALENEX)
%D 2017
%E Fekete, Sándor P.
%E Ramachandran, Vijaya
%I SIAM
%K from:leonkokkoliadis sfbtrr161 2017 B06
%P 185-196
%R 10.1137/1.9781611974768.15
%T Map Simplification with Topology Constraints: Exactly and in Practice
%U https://doi.org/10.1137/1.9781611974768.15
%X 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, and the recent GISCup competition.
%@ 978-1-61197-476-8
@inproceedings{conf/alenex/FunkeMMSW17,
abstract = {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, and the recent GISCup competition.},
added-at = {2020-03-05T13:01:05.000+0100},
author = {Funke, Stefan and Mendel, Thomas and Miller, Alexander and Storandt, Sabine and Wiebe, Maria},
biburl = {https://puma.ub.uni-stuttgart.de/bibtex/292fc63cf1df2d8ff2e70739c0ceb2c28/sfbtrr161},
booktitle = {Proceedings of the Meeting on Algorithm Engineering and Experiments (ALENEX)},
doi = {10.1137/1.9781611974768.15},
editor = {Fekete, Sándor P. and Ramachandran, Vijaya},
ee = {http://dx.doi.org/10.1137/1.9781611974768.15},
interhash = {63bda502f39bca425c58e3385c0195d2},
intrahash = {92fc63cf1df2d8ff2e70739c0ceb2c28},
isbn = {978-1-61197-476-8},
keywords = {from:leonkokkoliadis sfbtrr161 2017 B06},
pages = {185-196},
publisher = {SIAM},
timestamp = {2020-03-05T12:01:05.000+0100},
title = {Map Simplification with Topology Constraints: Exactly and in Practice},
url = {https://doi.org/10.1137/1.9781611974768.15},
year = 2017
}
