Document Open Access Logo

Simplification of Polyline Bundles

Authors Joachim Spoerhase , Sabine Storandt, Johannes Zink

PDF
Thumbnail PDF

File

LIPIcs.SWAT.2020.35.pdf
  • Filesize: 1.03 MB
  • 20 pages

Document Identifiers

Author Details

Joachim Spoerhase
  • Aalto University, Finland
  • University of Würzburg, Germany
Sabine Storandt
  • University of Konstanz, Germany
Johannes Zink
  • University of Würzburg, Germany

Funding

  • Spoerhase, Joachim: Funded by European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. 759557).
  • Storandt, Sabine: Funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – Project-ID 50974019 – TRR 161.

Cite As Get BibTex

Joachim Spoerhase, Sabine Storandt, and Johannes Zink. Simplification of Polyline Bundles. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 35:1-35:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.SWAT.2020.35

Abstract

We propose and study a generalization to the well-known problem of polyline simplification. Instead of a single polyline, we are given a set of l polylines possibly sharing some line segments and bend points. Our goal is to minimize the number of bend points in the simplified bundle with respect to some error tolerance δ (measuring Fréchet distance) but under the additional constraint that shared parts have to be simplified consistently. We show that polyline bundle simplification is NP-hard to approximate within a factor n^(1/3 - ε) for any ε > 0 where n is the number of bend points in the polyline bundle. This inapproximability even applies to instances with only l=2 polylines. However, we identify the sensitivity of the solution to the choice of δ as a reason for this strong inapproximability. In particular, we prove that if we allow δ to be exceeded by a factor of 2 in our solution, we can find a simplified polyline bundle with no more than 𝒪(log (l + n)) ⋅ OPT bend points in polytime, providing us with an efficient bi-criteria approximation. As a further result, we show fixed-parameter tractability in the number of shared bend points.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
  • Theory of computation → Computational geometry
  • Theory of computation → Problems, reductions and completeness
  • Theory of computation → Fixed parameter tractability
Keywords
  • Polyline Simplification
  • Bi-criteria Approximation
  • Hardness of Approximation
  • Geometric Set Cover

Metrics

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

References

  1. 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. URL: https://doi.org/10.1007/s00453-005-1165-y.
  2. Helmut Alt and Michael Godau. Computing the Fréchet distance between two polygonal curves. International Journal of Computational Geometry and Applications, 5:75-91, 1995. URL: https://doi.org/10.1142/S0218195995000064.
  3. Maike Buchin, Anne Driemel, and Bettina Speckmann. Computing the Fréchet distance with shortcuts is NP-hard. In Proceedings of the 30th Annual Symposium on Computational Geometry (SoCG'14), pages 367-376, 2014. URL: https://doi.org/10.1145/2582112.2582144.
  4. Maike Buchin, Bernhard Kilgus, and Andrea Kölzsch. Group diagrams for representing trajectories. In Proceedings of the 11th ACM SIGSPATIAL International Workshop on Computational Transportation Science, pages 1-10, 2018. Google Scholar
  5. W. S. Chan and F. Chin. Approximation of polygonal curves with minimum number of line segments or minimum error. International Journal of Computational Geometry and Applications, 6(1):59-77, 1996. URL: https://doi.org/10.1142/S0218195996000058.
  6. Marc de Berg, Marc J. van Kreveld, and Stefan Schirra. Topologically correct subdivision simplification using the bandwidth criterion. Cartography and Geographic Information Systems, 25(1):243-257, 1998. URL: https://doi.org/10.1559/152304098782383007.
  7. 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
  8. Regina Estkowski and Joseph SB Mitchell. Simplifying a polygonal subdivision while keeping it simple. In Proceedings of the 17th Annual Symposium on Computational Geometry (SoCG'01), pages 40-49. ACM, 2001. URL: https://doi.org/10.1145/378583.378612.
  9. Stefan Funke, Thomas Mendel, Alexander Miller, Sabine Storandt, and Maria Wiebe. Map simplification with topology constraints: Exactly and in practice. In Proceedings of the 19th Workshop on Algorithm Engineering and Experiments (ALENEX'17), pages 185-196. SIAM, 2017. Google Scholar
  10. Michael Godau. A natural metric for curves - computing the distance for polygonal chains and approximation algorithms. In Proceedings of the 8th Annual Symposium on Theoretical Aspects of Computer Science (STACS'91), pages 127-136, 1991. URL: https://doi.org/10.1007/BFb0020793.
  11. Magnús M. Halldórsson. Approximating the minimum maximal independence number. Information Processing Letters, 46(4):169-172, 1993. URL: https://doi.org/10.1016/0020-0190(93)90022-2.
  12. Songtao He, Favyen Bastani, Sofiane Abbar, Mohammad Alizadeh, Hari Balakrishnan, Sanjay Chawla, and Sam Madden. Roadrunner: improving the precision of road network inference from GPS trajectories. In Proceedings of the 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pages 3-12, 2018. Google Scholar
  13. John Hershberger and Jack Snoeyink. Speeding up the Douglas-Peucker line-simplification algorithm. In Proceedings of the 5th International Symposium on Spatial Data Handling (SDH'92), pages 134-143, 1992. Google Scholar
  14. Hiroshi Imai and Masao Iri. Polygonal approximations of a curve - formulations and algorithms. In Godfried T. Toussaint, editor, Computational Morphology, volume 6 of Machine Intelligence and Pattern Recognition, pages 71-86. North-Holland, 1988. URL: https://doi.org/10.1016/B978-0-444-70467-2.50011-4.
  15. David S. Johnson. Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences, 9(3):256-278, 1974. URL: https://doi.org/10.1016/S0022-0000(74)80044-9.
  16. Urs Ramer. An iterative procedure for the polygonal approximation of plane curves. Computer Graphics and Image Processing, 1(3):244-256, 1972. URL: https://doi.org/10.1016/S0146-664X(72)80017-0.
  17. Marc J. van Kreveld, Maarten Löffler, and Lionov Wiratma. On optimal polyline simplification using the Hausdorff and Fréchet distance. Journal of Computational Geometry, 11(1):1-25, 2020. URL: https://journals.carleton.ca/jocg/index.php/jocg/article/view/415.
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