On optimal polyline simplification using the Hausdorff and Fréchet distance
DOI10.4230/LIPICS.SOCG.2018.56zbMATH Open1473.68206OpenAlexW2963946018MaRDI QIDQ5115824FDOQ5115824
Maarten Löffler, Marc Van Kreveld, Lionov Wiratma
Publication date: 18 August 2020
Full work available at URL: https://dblp.uni-trier.de/db/conf/compgeom/compgeom2018.html#KreveldLW18
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
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)
Cites Work
- Some simplified NP-complete graph problems
- Every planar graph is the intersection graph of segments in the plane
- APPROXIMATING POLYGONS AND SUBDIVISIONS WITH MINIMUM-LINK PATHS
- COMPUTING THE FRÉCHET DISTANCE BETWEEN TWO POLYGONAL CURVES
- Map Simplification with Topology Constraints: Exactly and in Practice
- On the complexity of locating linear facilities in the plane
- Title not available (Why is that?)
- Approximate matching of polygonal shapes
- Near-linear time approximation algorithms for curve simplification
- Efficiently approximating polygonal paths in three and higher dimensions
- Title not available (Why is that?)
- APPROXIMATION OF POLYGONAL CURVES WITH MINIMUM NUMBER OF LINE SEGMENTS OR MINIMUM ERROR
- Title not available (Why is that?)
- Simplifying a polygonal subdivision while keeping it simple
- Optimal simplification of polygonal chain for rendering
- Polygonal path simplification with angle constraints
- Title not available (Why is that?)
- On Optimal Polyline Simplification Using the Hausdorff and Fréchet Distance
- Streaming algorithms for line simplification
Cited In (12)
- Title not available (Why is that?)
- Global Curve Simplification
- 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
- Title not available (Why is that?)
- Fréchet Distance for Uncertain Curves
- Streaming algorithms for line simplification
- Title not available (Why is that?)
- Embedding ray intersection graphs and global curve simplification
- Place the Vertices Anywhere on the Curve and Simplify
- Simplifying 3D Polygonal Chains Under the Discrete Fréchet Distance
- A Near-Linear Time Guaranteed Algorithm for Digital Curve Simplification under the Fréchet Distance
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)
