Simplifying a polygonal subdivision while keeping it simple
Regina Estkowski, Joseph S. B. Mitchell · 2001
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 simpli- ed 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 simplication 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 dicult to solve, even approximately: we show that it is MIN PB-complete and that, in particular, assuming P 6= 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 propose some heuristic methods for solving the problem, which we have implemented. Our experimental results show that, in practice, we get quite good simplications in a reasonable amount of time. Keywords polygonal subdivisions, simplication, map generalization, geographic information systems, approximation algorithms 1.