Simplifying a polygonal subdivision while keeping it simple

We study the problem of simplifying a polygonal subdivision, subject to a given error bound, ε, and subject to maintaining the topology of the input, while not introducing new (Steiner) vertices. In particular, we require that the simplified chains may not cross themselves or cross other chains. In GIS applications, for example, we are interested in simplifying the banks of a river without the left and right banks getting "tangled" and without "islands" becoming part of the land mass. Maintaining topology during subdivision simplification is an important constraint in many real GIS applications. We give both theoretical and experimental results. (a). We prove that the general problem we are trying to solve is in fact difficult to solve, even approximately: we show that it is MIN PB-complete and that, in particular, assuming P ≠ NP, in the general case we cannot obtain in polynomial time an approximation within a factor n^1/5-δ of an optimal solution. (b). We pr opose some heuristic methods for solving the problem, which we have implemented. Our experimental results show that, in practice, we get quite good simplifications in a reasonable amount of time.