Map Simplification with Topology Constraints: Exactly and in Practice

摘要

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 inapprox-imability 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].