English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  Topologically correct subdivision simplification using the bandwidth criterion

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.

Item is

Files

show Files

Locators

show

Creators

show
hide
 Creators:
de Berg, Marc, Author
van Kreveld, Marc, Author
Schirra, Stefan1, Author           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 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.

Details

show
hide
Language(s): eng - English
 Dates: 2010-03-021998
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: Peer
 Identifiers: eDoc: 517976
Other: Local-ID: C1256428004B93B8-CF956027D7E0F59EC125671600492704-deBerg-vanKreveld-Schirra1998
 Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show
hide
Title: Cartography and Geographic Information Systems
Source Genre: Journal
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 25 (4) Sequence Number: - Start / End Page: 243 - 257 Identifier: -