de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch

Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt

# Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Zeitschriftenartikel

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

##### MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons45391

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

##### Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
##### Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
##### Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
##### Zitation

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.

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.