Map simplification with topology constraints: Exactly and in practice
S Funke, T Mendel, A Miller, S Storandt… - 2017 Proceedings of the …, 2017 - SIAM
S Funke, T Mendel, A Miller, S Storandt, M Wiebe
2017 Proceedings of the Ninteenth Workshop on Algorithm Engineering and …, 2017•SIAMWe 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 …
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 …
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].
Society for Industrial and Applied Mathematics