English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse
  1. View item / 
  2. Item Summary

Item

ITEM ACTIONSEXPORT
Add to Basket
  Local TagsRelease HistoryDetailsSummary

Released
Journal Article

Topologically correct subdivision simplification using the bandwidth criterion

MPS-Authors
/persons/resource/persons45391

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

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)
There are no public fulltexts stored in PuRe
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: https://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.