Progressive simplification of polygonal curves

Kevin A. Buchin, M.P. Konzack, Wim W.T. Reddingius

Research output: Contribution to journalArticleAcademic

45 Downloads (Pure)


Simplifying polygonal curves at different levels of detail is an important problem with many applications. Existing geometric optimization algorithms are only capable of minimizing the complexity of a simplified curve for a single level of detail. We present an O(n3m)-time algorithm that takes a polygonal curve of n vertices and produces a set of consistent simplifications for m scales while minimizing the cumulative simplification complexity. This algorithm is compatible with distance measures such as the Hausdorff, the Fréchet and area-based distances, and enables simplification for continuous scaling in O(n5) time. To speed up this algorithm in practice, we present new techniques for constructing and representing so-called shortcut graphs. Experimental evaluation of these techniques on trajectory data reveals a significant improvement of using shortcut graphs for progressive and non-progressive curve simplification, both in terms of running time and memory usage.
Original languageEnglish
Article number1806.02647v1
Number of pages20
Publication statusPublished - 2018


  • Computational Geometry


Dive into the research topics of 'Progressive simplification of polygonal curves'. Together they form a unique fingerprint.

Cite this