Near-linear time approximation algorithms for curve simplification

DOI10.1007/s00453-005-1165-yzbMath1086.68134OpenAlexW2162911459MaRDI QIDQ818650

Nabil H. Mustafa, Pankaj K. Agarwal, Yusu Wang, Sariel Har-Peled

Publication date: 21 March 2006

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-005-1165-y

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Approximation algorithms (68W25)

Related Items (15)

Embedding ray intersection graphs and global curve simplification ⋮ Four Soviets walk the dog: improved bounds for computing the Fréchet distance ⋮ Unnamed Item ⋮ Approximating the Fréchet distance for realistic curves in near linear time ⋮ Computing homotopic line simplification ⋮ Place the Vertices Anywhere on the Curve and Simplify ⋮ VORONOI DIAGRAM OF POLYGONAL CHAINS UNDER THE DISCRETE FRÉCHET DISTANCE ⋮ Unnamed Item ⋮ On the Hardness of Orthogonal-Order Preserving Graph Drawing ⋮ Simplifying 3D Polygonal Chains Under the Discrete Fréchet Distance ⋮ Global Curve Simplification ⋮ Streaming algorithms for line simplification ⋮ Progressive simplification of polygonal curves ⋮ On Optimal Polyline Simplification Using the Hausdorff and Fréchet Distance ⋮ A Fast Approximate Skeleton with Guarantees for Any Cloud of Points in a Euclidean Space

This page was built for publication: Near-linear time approximation algorithms for curve simplification