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

Hausdorff distancepolygonal line simplificationDouglas-PeuckerFréchet distanceImai-Iri

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) 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

• 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?)
• APPROXIMATING POLYGONS AND SUBDIVISIONS WITH MINIMUM-LINK PATHS
• APPROXIMATION OF POLYGONAL CURVES WITH MINIMUM NUMBER OF LINE SEGMENTS OR MINIMUM ERROR
• Approximate matching of polygonal shapes
• 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)
• 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

(18)

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

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)