de.mpg.escidoc.pubman.appbase.FacesBean
English

# Item

ITEM ACTIONSEXPORT

Released

Journal Article

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

##### MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons45391

Schirra,  Stefan
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

##### 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.