Document Open Access Logo

Polyline Simplification has Cubic Complexity

Authors Karl Bringmann, Bhaskar Ray Chaudhury

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2019.18.pdf
  • Filesize: 0.8 MB
  • 16 pages

Document Identifiers

Author Details

Karl Bringmann
  • Max Planck Institute for Informatics, Saarland Informatics Campus, Saarbrücken, Germany
Bhaskar Ray Chaudhury
  • Max Planck Institute for Informatics, Saarland Informatics Campus, Saarbrücken, Germany
  • Graduate School of Computer Science Saarbrücken, Saarland Informatics Campus, Germany

Cite As Get BibTex

Karl Bringmann and Bhaskar Ray Chaudhury. Polyline Simplification has Cubic Complexity. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 18:1-18:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.SoCG.2019.18

Abstract

In the classic polyline simplification problem we want to replace a given polygonal curve P, consisting of n vertices, by a subsequence P' of k vertices from P such that the polygonal curves P and P' are "close". Closeness is usually measured using the Hausdorff or Fréchet distance. These distance measures can be applied globally, i.e., to the whole curves P and P', or locally, i.e., to each simplified subcurve and the line segment that it was replaced with separately (and then taking the maximum). We provide an O(n^3) time algorithm for simplification under Global-Fréchet distance, improving the previous best algorithm by a factor of Omega(kn^2). We also provide evidence that in high dimensions cubic time is essentially optimal for all three problems (Local-Hausdorff, Local-Fréchet, and Global-Fréchet). Specifically, improving the cubic time to O(n^{3-epsilon} poly(d)) for polyline simplification over (R^d,L_p) for p = 1 would violate plausible conjectures. We obtain similar results for all p in [1,infty), p != 2. In total, in high dimensions and over general L_p-norms we resolve the complexity of polyline simplification with respect to Local-Hausdorff, Local-Fréchet, and Global-Fréchet, by providing new algorithms and conditional lower bounds.

Subject Classification

ACM Subject Classification
  • Theory of computation
  • Theory of computation → Design and analysis of algorithms
  • Theory of computation → Mathematical optimization
Keywords
  • Polyline simplification
  • Fréchet distance
  • Hausdorff distance
  • Conditional lower bounds

Metrics

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

Related Versions

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. Amir Abboud, Virginia Vassilevska Williams, and Joshua R. Wang. Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs. In SODA, pages 377-391. SIAM, 2016. Google Scholar
  3. Pankaj K. Agarwal, Sariel Har-Peled, Nabil H. Mustafa, and Yusu Wang. Near-Linear Time Approximation Algorithms for Curve Simplification. Algorithmica, 42(3-4):203-219, 2005. Google Scholar
  4. Helmut Alt, Alon Efrat, Günter Rote, and Carola Wenk. Matching planar maps. In SODA, pages 589-598. ACM/SIAM, 2003. Google Scholar
  5. Helmut Alt and Michael Godau. Computing the Fréchet distance between two polygonal curves. Internat. J. Comput. Geom. Appl., 5(1-2):78-99, 1995. Google Scholar
  6. 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
  7. Kevin Buchin, Maike Buchin, Maximilian Konzack, Wolfgang Mulzer, and André Schulz. Fine-grained analysis of problems on curves. EuroCG, Lugano, Switzerland, 2016. 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. Comput. Geom., 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 SoCG, pages 40-49. ACM, 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 ALENEX, pages 185-196. SIAM, 2017. Google Scholar
  14. Jiawei Gao, Russell Impagliazzo, Antonina Kolokolova, and R. Ryan Williams. Completeness for First-Order Properties on Sparse Structures with Algorithmic Applications. In SODA, pages 2162-2181. SIAM, 2017. Google Scholar
  15. Michael Godau. A natural metric for curves - computing the distance for polygonal chains and approximation algorithms. In STACS, pages 127-136, 1991. Google Scholar
  16. Leonidas J. Guibas, John Hershberger, Joseph S. B. Mitchell, and Jack Snoeyink. Approximating Polygons and Subdivisions with Minimum Link Paths. Int. J. Comput. Geometry Appl., 3(4):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 SoCG, pages 383-384. ACM, 1994. Google Scholar
  18. Hiroshi Imai and Masao Iri. Polygonal Approximations of a Curve — Formulations and Algorithms. In Computational Morphology, volume 6 of Machine Intelligence and Pattern Recognition, pages 71-86. North-Holland, 1988. Google Scholar
  19. Avraham Melkman and Joseph O'Rourke. On Polygonal Chain Approximation. In Computational Morphology, volume 6 of Machine Intelligence and Pattern Recognition, pages 87-95. North-Holland, 1988. Google Scholar
  20. Marc J. van Kreveld, Maarten Löffler, and Lionov Wiratma. On Optimal Polyline Simplification Using the Hausdorff and Fréchet Distance. In SoCG, volume 99 of LIPIcs, pages 56:1-56:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  21. Virginia Vassilevska Williams. On some fine-grained questions in algorithms and complexity. In Proceedings of the ICM, 2018. Google Scholar
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