On optimal polyline simplification using the Hausdorff and Fréchet distance

DOI10.4230/LIPICS.SOCG.2018.56MaRDI QIDQ5115824zbMATH OpenOpenAlexFDO

Authors Maarten Löffler, Lionov Wiratma, Marc Van Kreveld

Publication date 18 August 2020

Full work available at URL https://dblp.uni-trier.de/db/conf/compgeom/compgeom2018.html#KreveldLW18

zbMATH Keywords

Douglas-PeuckerFréchet distanceHausdorff distanceImai-Iripolygonal line simplification

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• On optimal polyline simplification using the Hausdorff and Fréchet distance
• Polyline simplification has cubic complexity
• scientific article; zbMATH DE number 1947379
• Near-linear time approximation algorithms for curve simplification
• A Near-Linear Time Guaranteed Algorithm for Digital Curve Simplification under the Fréchet Distance

Cites work

• Approximate matching of polygonal shapes
• APPROXIMATING POLYGONS AND SUBDIVISIONS WITH MINIMUM-LINK PATHS
• APPROXIMATION OF POLYGONAL CURVES WITH MINIMUM NUMBER OF LINE SEGMENTS OR MINIMUM ERROR
• COMPUTING THE FRÉCHET DISTANCE BETWEEN TWO POLYGONAL CURVES
• Efficiently approximating polygonal paths in three and higher dimensions
• Every planar graph is the intersection graph of segments in the plane (extended abstract)
• scientific article; zbMATH DE number 1670858 (Why is no real title available?)
• scientific article; zbMATH DE number 4074316 (Why is no real title available?)
• scientific article; zbMATH DE number 4082817 (Why is no real title available?)
• scientific article; zbMATH DE number 176499 (Why is no real title available?)
• Map simplification with topology constraints: exactly and in practice
• Near-linear time approximation algorithms for curve simplification
• On optimal polyline simplification using the Hausdorff and Fréchet distance
• On the complexity of locating linear facilities in the plane
• Optimal simplification of polygonal chain for rendering
• Polygonal path simplification with angle constraints
• Simplifying a polygonal subdivision while keeping it simple
• Some simplified NP-complete graph problems
• Streaming algorithms for line simplification

Cited in

(20)

• Embedding ray intersection graphs and global curve simplification
• A Near-Linear Time Guaranteed Algorithm for Digital Curve Simplification under the Fréchet Distance
• scientific article; zbMATH DE number 2185597 (Why is no real title available?)
• On optimal polyline simplification using the Hausdorff and Fréchet distance
• Front Matter, Table of Contents, Foreword, Conference Organization, Additional Reviewers, Acknowledgement of Support, Invited Talks
• Mapping polygons to the grid with small Hausdorff and Fréchet distance
• On the general chain pair simplification problem
• Global Curve Simplification
• Polyline simplification has cubic complexity
• On optimal polyline simplification using the Hausdorff and Fréchet distance
• Place the vertices anywhere on the curve and simplify
• Map simplification with topology constraints: exactly and in practice
• Simplifying 3D Polygonal Chains Under the Discrete Fréchet Distance
• Polyline simplification has cubic complexity
• Streaming algorithms for line simplification
• Streaming algorithms for line simplification
• Fréchet Distance for Uncertain Curves
• Computing realistic terrains from imprecise elevations
• Minimum-complexity graph simplification under the Fréchet-like distance
• Simplification of trajectory streams

This page was built for publication: On optimal polyline simplification using the Hausdorff and Fréchet distance

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