Topologically correct subdivision simplification using the bandwidth criterion

M. Berg, de, M.J. Kreveld, van, S. Schirra

Research output: Contribution to journalArticleAcademicpeer-review

58 Citations (Scopus)


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.
Original languageEnglish
Pages (from-to)243-257
JournalCartography and Geographic Information Science
Issue number4
Publication statusPublished - 1998
Externally publishedYes

Fingerprint Dive into the research topics of 'Topologically correct subdivision simplification using the bandwidth criterion'. Together they form a unique fingerprint.

Cite this