Document Open Access Logo

On Optimal Polyline Simplification Using the Hausdorff and Fréchet Distance

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

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2018.56.pdf
  • Filesize: 0.78 MB
  • 14 pages

Document Identifiers

Author Details

Marc van Kreveld
Maarten Löffler
Lionov Wiratma

Cite As Get BibTex

Marc van Kreveld, Maarten Löffler, and Lionov Wiratma. On Optimal Polyline Simplification Using the Hausdorff and Fréchet Distance. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 56:1-56:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.SoCG.2018.56

Abstract

We revisit the classical polygonal line simplification problem and study it using the Hausdorff distance and Fréchet distance. Interestingly, no previous authors studied line simplification under these measures in its pure form, namely: for a given epsilon>0, choose a minimum size subsequence of the vertices of the input such that the Hausdorff or Fréchet distance between the input and output polylines is at most epsilon.
We analyze how the well-known Douglas-Peucker and Imai-Iri simplification algorithms perform compared to the optimum possible, also in the situation where the algorithms are given a considerably larger error threshold than epsilon. Furthermore, we show that computing an optimal simplification using the undirected Hausdorff distance is NP-hard. The same holds when using the directed Hausdorff distance from the input to the output polyline, whereas the reverse can be computed in polynomial time. Finally, to compute the optimal simplification from a polygonal line consisting of n vertices under the Fréchet distance, we give an O(kn^5) time algorithm that requires O(kn^2) space, where k is the output complexity of the simplification.

Subject Classification

Keywords
  • polygonal line simplification
  • Hausdorff distance
  • Fréchet distance
  • Imai-Iri
  • Douglas-Peucker

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Mohammad Ali Abam, Mark de Berg, Peter Hachenberger, and Alireza Zarei:. Streaming algorithms for line simplification. Discrete & Computational Geometry, 43(3):497-515, 2010. Google Scholar
  2. Pankaj K. Agarwal, Sariel Har-Peled, Nabil H. Mustafa, and Yusu Wang. Near-linear time approximation algorithms for curve simplification. Algorithmica, 42(3):203-219, 2005. Google Scholar
  3. Helmut Alt, Bernd Behrends, and Johannes Blömer. Approximate matching of polygonal shapes. Annals of Mathematics and Artificial Intelligence, 13(3):251-265, Sep 1995. Google Scholar
  4. Helmut Alt and Michael Godau. Computing the Fréchet distance between two polygonal curves. International Journal of Computational Geometry & Applications, 5(1-2):75-91, 1995. Google Scholar
  5. Gill Barequet, Danny Z. Chen, Ovidiu Daescu, Michael T. Goodrich, and Jack Snoeyink. Efficiently approximating polygonal paths in three and higher dimensions. Algorithmica, 33(2):150-167, 2002. Google Scholar
  6. Lilian Buzer. Optimal simplification of polygonal chain for rendering. In Proceedings 23rd Annual ACM Symposium on Computational Geometry, SCG '07, pages 168-174, 2007. Google Scholar
  7. Jérémie Chalopin and Daniel Gonçalves. Every planar graph is the intersection graph of segments in the plane: Extended abstract. In Proceedings 41st Annual ACM Symposium on Theory of Computing, STOC '09, pages 631-638, 2009. Google Scholar
  8. W.S. Chan and F. Chin. Approximation of polygonal curves with minimum number of line segments or minimum error. International Journal of Computational Geometry & Applications, 06(01):59-77, 1996. Google Scholar
  9. Danny Z. Chen, Ovidiu Daescu, John Hershberger, Peter M. Kogge, Ningfang Mi, and Jack Snoeyink. Polygonal path simplification with angle constraints. Computational Geometry, 32(3):173-187, 2005. Google Scholar
  10. Mark de Berg, Marc van Kreveld, and Stefan Schirra. Topologically correct subdivision simplification using the bandwidth criterion. Cartography and Geographic Information Systems, 25(4):243-257, 1998. Google Scholar
  11. David H. Douglas and Thomas K. Peucker. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. Cartographica, 10(2):112-122, 1973. Google Scholar
  12. Regina Estkowski and Joseph S. B. Mitchell. Simplifying a polygonal subdivision while keeping it simple. In Proceedings 17th Annual ACM Symposium on Computational Geometry, SCG '01, pages 40-49, 2001. Google Scholar
  13. Stefan Funke, Thomas Mendel, Alexander Miller, Sabine Storandt, and Maria Wiebe. Map simplification with topology constraints: Exactly and in practice. In Proc. 19th Workshop on Algorithm Engineering and Experiments (ALENEX), pages 185-196, 2017. Google Scholar
  14. M.R. Garey, D.S. Johnson, and L. Stockmeyer. Some simplified NP-complete graph problems. Theoretical Computer Science, 1(3):237-267, 1976. Google Scholar
  15. Michael Godau. A natural metric for curves - computing the distance for polygonal chains and approximation algorithms. In Proceedings 8th Annual Symposium on Theoretical Aspects of Computer Science, STACS 91, pages 127-136. Springer-Verlag, 1991. Google Scholar
  16. Leonidas J. Guibas, John E. Hershberger, Joseph S.B. Mitchell, and Jack Scott Snoeyink. Approximating polygons and subdivisions with minimum-link paths. International Journal of Computational Geometry & Applications, 03(04):383-415, 1993. Google Scholar
  17. John Hershberger and Jack Snoeyink. An O(n log n) implementation of the Douglas-Peucker algorithm for line simplification. In Proceedings 10th Annual ACM Symposium on Computational Geometry, SCG '94, pages 383-384, 1994. Google Scholar
  18. Hiroshi Imai and Masao Iri. Polygonal approximations of a curve - formulations and algorithms. In Godfried T. Toussaint, editor, Computational Morphology: A Computational Geometric Approach to the Analysis of Form. North-Holland, Amsterdam, 1988. Google Scholar
  19. V. S. Anil Kumar, Sunil Arya, and H. Ramesh. Hardness of set cover with intersection 1. In Automata, Languages and Programming: 27th International Colloquium, ICALP 2000, pages 624-635. Springer, Berlin, Heidelberg, 2000. Google Scholar
  20. Nimrod Megiddo and Arie Tamir. On the complexity of locating linear facilities in the plane. Operations Research Letters, 1(5):194-197, 1982. Google Scholar
  21. Avraham Melkman and Joseph O'Rourke. On polygonal chain approximation. In Godfried T. Toussaint, editor, Computational Morphology: A Computational Geometric Approach to the Analysis of Form, pages 87-95. North-Holland, Amsterdam, 1988. Google Scholar
  22. E. R. Scheinerman. Intersection Classes and Multiple Intersection Parameters of Graphs. PhD thesis, Princeton University, 1984. Google Scholar
  23. Marc van Kreveld, Maarten Löffler, and Lionov Wiratma. On optimal polyline simplification using the hausdorff and fréchet distance. URL: https://arxiv.org/abs/1803.03550.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact