Near-linear time approximation algorithms for curve simplification

DOI10.1007/S00453-005-1165-YzbMATH Open1086.68134OpenAlexW2162911459MaRDI QIDQ818650FDOQ818650

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

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

Recommendations

• scientific article; zbMATH DE number 1947379
• SPACE-EFFICIENT ALGORITHMS FOR APPROXIMATING POLYGONAL CURVES IN TWO-DIMENSIONAL SPACE
• A Near-Linear Time Guaranteed Algorithm for Digital Curve Simplification under the Fréchet Distance
• scientific article; zbMATH DE number 1222818
• Efficient algorithms for approximating polygonal chains

Mathematics Subject Classification ID

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

Cited In (32)

• Title not available (Why is that?)
• Global Curve Simplification
• Title not available (Why is that?)
• Robust nonparametric simplification of polygonal chains
• SimpliPoly: curvature-based polygonal curve simplification
• Title not available (Why is that?)
• Polyline simplification has cubic complexity
• Four Soviets walk the dog: improved bounds for computing the Fréchet distance
• Streaming algorithms for line simplification
• Speeding up simplification of polygonal curves using nested approximations
• On the Hardness of Orthogonal-Order Preserving Graph Drawing
• Voronoi diagram of polygonal chains under the discrete Fréchet distance
• Computing homotopic line simplification
• Linear-time algorithms for testing the realisability of line drawings of curved objects
• A fast approximate skeleton with guarantees for any cloud of points in a Euclidean space
• On optimal polyline simplification using the Hausdorff and Fréchet distance
• Approximating the Fréchet distance for realistic curves in near linear time
• Streaming algorithms for line simplification
• Progressive simplification of polygonal curves
• Embedding ray intersection graphs and global curve simplification
• SPACE-EFFICIENT ALGORITHMS FOR APPROXIMATING POLYGONAL CURVES IN TWO-DIMENSIONAL SPACE
• Simplifying 3D Polygonal Chains Under the Discrete Fréchet Distance
• Optimal simplification of polygonal chain for rendering
• Title not available (Why is that?)
• On optimal polyline simplification using the Hausdorff and Fréchet distance
• Title not available (Why is that?)
• Robust nonparametric data approximation of point sets via data reduction
• Universal approximate simplification under the discrete Fréchet distance
• Reduced-search dynamic programming for approximation of polygonal curves
• Optimal simplification of polygonal chains for subpixel-accurate rendering
• Place the vertices anywhere on the curve and simplify
• A Near-Linear Time Guaranteed Algorithm for Digital Curve Simplification under the Fréchet Distance

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

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