A new approach to subdivision simplification
Marc de Berg, Marc J. van Kreveld, Stefan Schirra · 1995
The line simplification problem is an old and well-studied problem in cartography. Although there are several algorithms to compute a simplification, there seem to be no algorithms that perform line simplification in the context of other geographical objects. This paper presents a nearly quadratic time algorithm for the following line simplification problem: Given a polygonal line, a set of extra points, and a real > 0, compute a simplification that guarantees (i) a maximum error, (ii) that the extra points remain on the same side of the simplified chain as of the original chain, and (iii) that the simplified chain has no self-intersections. The algorithm is applied as the main subroutine for subdivision simplification.