Simplification of Polyline Bundles
share
We propose and study generalizations to the well-known problem of polyline simplification. Instead of a single polyline, we are given a set of polylines possibly sharing some line segments and bend points. The simplification of those shared parts has to be consistent among the polylines. We consider two optimization goals: either minimizing the number of line segments or minimizing the number of bend points in the simplification. By reduction from Minimum-Independent-Dominating-Set, we show that both of these optimization problems are NP-hard to approximate within a factor n^1/3 - ε for any ε > 0 where n is the number of bend points in the polyline bundle. Moreover, we outline that both problems remain NP-hard even if the input is planar. On the positive side, we give a polynomial-size integer linear program and show fixed-parameter tractability in the number of shared bend points.
READ FULL TEXT