Topologically Correct Subdivision Simplification Using the Bandwidth Criterion

Publisher Website
Google Scholar
Abstract
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 and guarantees that the resulting subdivision is topologically correct.

This publication has 0 references indexed in Scilit: