# Item

ITEM ACTIONSEXPORT

Released

Journal Article

#### Topologically correct subdivision simplification using the bandwidth criterion

##### Locator

There are no locators available

##### Fulltext (public)

There are no public fulltexts available

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

de Berg, M., van Kreveld, M., & Schirra, S. (1998). Topologically correct subdivision
simplification using the bandwidth criterion.* Cartography and Geographic Information Systems,*
*25*(4), 243-257.

Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-37FE-8

##### Abstract

The line simplification problem is an old and well studied
problem in cartography. Although there are several algorithms to compute a
simplification there seems 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 $\epsilon > 0$, compute a
simplification that guarantees (i) a maximum error $\epsilon$; (ii) that the
extra points remain on the same side of the simplified chain as on 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.