Progressive simplification of polygonal curves

DOI10.1016/J.COMGEO.2020.101620zbMATH Open1432.68500arXiv1806.02647OpenAlexW3004917642MaRDI QIDQ2306367FDOQ2306367

Authors: Kevin Buchin, Maximilian Konzack, Wim Reddingius 

Publication date: 23 March 2020

Published in: Computational Geometry (Search for Journal in Brave)

Abstract: 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(n^{3}m)$-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'echet and area-based distances, and enables simplification for continuous scaling in $O(n^5)$ 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.

Full work available at URL: https://arxiv.org/abs/1806.02647

Recommendations

• scientific article; zbMATH DE number 1947379
• Near-linear time approximation algorithms for curve simplification
• SimpliPoly: curvature-based polygonal curve simplification
• Speeding up simplification of polygonal curves using nested approximations
• On optimal polyline simplification using the Hausdorff and Fréchet distance

zbMATH Keywords

computational geometrycurve simplificationline simplification

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites Work

• A note on two problems in connexion with graphs
• COMPUTING THE FRÉCHET DISTANCE BETWEEN TWO POLYGONAL CURVES
• Near-linear time approximation algorithms for curve simplification
• The pairing heap: A new form of self-adjusting heap
• A Fast $O(N)$ Multiresolution Polygonal Approximation Algorithm for GPS Trajectory Simplification
• Incremental algorithms for minimal length paths
• Title not available (Why is that?)
• APPROXIMATION OF POLYGONAL CURVES WITH MINIMUM NUMBER OF LINE SEGMENTS OR MINIMUM ERROR
• Area-preserving approximations of polygonal paths
• Distance-preserving approximations of polygonal paths

Cited In (11)

• Simplifying massive planar subdivisions
• Compressing spatio-temporal trajectories
• SimpliPoly: curvature-based polygonal curve simplification
• Polyline simplification has cubic complexity
• Speeding up simplification of polygonal curves using nested approximations
• Geodesic-preserving polygon simplification
• Straightening polygonal arcs and convexifying polygonal cycles
• Uncertain Curve Simplification
• Area-preserving subdivision simplification with topology constraints: exactly and in practice
• Shortcut hulls: vertex-restricted outer simplifications of polygons
• Place the vertices anywhere on the curve and simplify

This page was built for publication: Progressive simplification of polygonal curves

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2306367)