de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

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.