Document Open Access Logo

Uncertain Curve Simplification

Authors Kevin Buchin , Maarten Löffler, Aleksandr Popov , Marcel Roeloffzen

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2021.26.pdf
  • Filesize: 0.95 MB
  • 22 pages

Document Identifiers

Author Details

Kevin Buchin
  • Department of Mathematics and Computer Science, TU Eindhoven, The Netherlands
Maarten Löffler
  • Department of Information and Computing Sciences, Utrecht University, The Netherlands
Aleksandr Popov
  • Department of Mathematics and Computer Science, TU Eindhoven, The Netherlands
Marcel Roeloffzen
  • Department of Mathematics and Computer Science, TU Eindhoven, The Netherlands

Funding

  • Löffler, Maarten: Partially supported by the Dutch Research Council (NWO) under project no. 614.001.504.
  • Popov, Aleksandr: Supported by the Dutch Research Council (NWO) under project no. 612.001.801.
  • Roeloffzen, Marcel: Supported by the Dutch Research Council (NWO) under project no. 628.011.005.

Cite As Get BibTex

Kevin Buchin, Maarten Löffler, Aleksandr Popov, and Marcel Roeloffzen. Uncertain Curve Simplification. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 26:1-26:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.MFCS.2021.26

Abstract

We study the problem of polygonal curve simplification under uncertainty, where instead of a sequence of exact points, each uncertain point is represented by a region which contains the (unknown) true location of the vertex. The regions we consider are disks, line segments, convex polygons, and discrete sets of points. We are interested in finding the shortest subsequence of uncertain points such that no matter what the true location of each uncertain point is, the resulting polygonal curve is a valid simplification of the original polygonal curve under the Hausdorff or the Fréchet distance. For both these distance measures, we present polynomial-time algorithms for this problem.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • Curves
  • Uncertainty
  • Simplification
  • Fréchet Distance
  • Hausdorff Distance

Metrics

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

Related Versions

References

  1. Pankaj K. Agarwal, Boris Aronov, Sariel Har-Peled, Jeff M. Phillips, Ke Yi, and Wuzhou Zhang. Nearest-neighbor searching under uncertainty II. ACM Transactions on Algorithms, 13(1):3:1-3:25, December 2016. URL: https://doi.org/10.1145/2955098.
  2. Pankaj K. Agarwal, Alon Efrat, Swaminathan Sankararaman, and Wuzhou Zhang. Nearest-neighbor searching under uncertainty I. Discrete & Computational Geometry, 58(3):705-745, July 2017. URL: https://doi.org/10.1007/s00454-017-9903-x.
  3. 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. URL: https://doi.org/10.1007/s00453-005-1165-y.
  4. Pankaj K. Agarwal and Kasturi R. Varadarajan. Efficient algorithms for approximating polygonal chains. Discrete & Computational Geometry, 23(2):273-291, 2000. URL: https://doi.org/10.1007/PL00009500.
  5. Hee-Kap Ahn, Christian Knauer, Marc Scherfenberg, Lena Schlipf, and Antoine Vigneron. Computing the discrete Fréchet distance with imprecise input. International Journal of Computational Geometry & Applications, 22(01):27-44, 2012. URL: https://doi.org/10.1142/S0218195912600023.
  6. Sander P. A. Alewijnse, Kevin Buchin, Maike Buchin, Stef Sijben, and Michel A. Westenberg. Model-based segmentation and classification of trajectories. Algorithmica, 80(8):2422-2452, 2018. URL: https://doi.org/10.1007/s00453-017-0329-x.
  7. Gill Barequet, Danny Z. Chen, Ovidiu Daescu, Michael T. Goodrich, and Jack S. Snoeyink. Efficiently approximating polygonal paths in three and higher dimensions. Algorithmica, 33(2):150-167, 2002. URL: https://doi.org/10.1007/s00453-001-0096-5.
  8. Karl Bringmann and Bhaskar Ray Chaudhury. Polyline simplification has cubic complexity. In 35th International Symposium on Computational Geometry (SoCG 2019), volume 129 of Leibniz International Proceedings in Informatics (LIPIcs), pages 18:1-18:16, Dagstuhl, Germany, 2019. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.SoCG.2019.18.
  9. Kevin Buchin, Chenglin Fan, Maarten Löffler, Aleksandr Popov, Benjamin Raichel, and Marcel Roeloffzen. Fréchet distance for uncertain curves. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), volume 168 of Leibniz International Proceedings in Informatics (LIPIcs), pages 20:1-20:20, Dagstuhl, Germany, 2020. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.ICALP.2020.20.
  10. Kevin Buchin, Maximilian Konzack, and Wim Reddingius. Progressive simplification of polygonal curves. Computational Geometry: Theory & Applications, 88:101620:1-101620:18, 2020. URL: https://doi.org/10.1016/j.comgeo.2020.101620.
  11. Kevin Buchin, Maarten Löffler, Pat Morin, and Wolfgang Mulzer. Preprocessing imprecise points for Delaunay triangulation: Simplified and extended. Algorithmica, 61(3):674-693, November 2011. URL: https://doi.org/10.1007/s00453-010-9430-0.
  12. Kevin Buchin, Maarten Löffler, Aleksandr Popov, and Marcel Roeloffzen. Uncertain curve simplification, 2021. URL: http://arxiv.org/abs/2103.09223.
  13. Kevin Buchin, Stef Sijben, T. Jean Marie Arseneau, and Erik P. Willems. Detecting movement patterns using Brownian bridges. In Proceedings of the 20th International Conference on Advances in Geographic Information Systems (SIGSPATIAL '12), pages 119-128, New York, NY, USA, 2012. ACM. URL: https://doi.org/10.1145/2424321.2424338.
  14. Maike Buchin and Stef Sijben. Discrete Fréchet distance for uncertain points, 2016. Presented at EuroCG 2016, Lugano, Switzerland. URL: http://www.eurocg2016.usi.ch/sites/default/files/paper_72.pdf [cited 2019-07-10].
  15. Leizhen Cai and Mark Keil. Computing visibility information in an inaccurate simple polygon. International Journal of Computational Geometry & Applications, 7:515-538, 1997. URL: https://doi.org/10.1142/S0218195997000326.
  16. W. S. Chan and Francis Chin. Approximation of polygonal curves with minimum number of line segments or minimum error. International Journal of Computational Geometry & Applications, 6(1):59-77, 1996. URL: https://doi.org/10.1142/S0218195996000058.
  17. 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: The International Journal for Geographic Information and Geovisualization, 10(2):112-122, 1973. URL: https://doi.org/10.3138/FM57-6770-U75U-7727.
  18. Anne Driemel, Herman Haverkort, Maarten Löffler, and Rodrigo I. Silveira. Flow computations on imprecise terrains. Journal of Computational Geometry, 4(1):38-78, 2013. URL: https://doi.org/10.20382/jocg.v4i1a3.
  19. William Evans, David Kirkpatrick, Maarten Löffler, and Frank Staals. Competitive query strategies for minimising the ply of the potential locations of moving points. In Proceedings of the 29th Annual Symposium on Computational Geometry (SoCG '13'), pages 155-164, New York, NY, USA, 2013. ACM. URL: https://doi.org/10.1145/2462356.2462395.
  20. Chris Gray, Frank Kammer, Maarten Löffler, and Rodrigo I. Silveira. Removing local extrema from imprecise terrains. Computational Geometry: Theory & Applications, 45(7):334-349, 2012. URL: https://doi.org/10.1016/j.comgeo.2012.02.002.
  21. Joachim Gudmundsson, Jyrki Katajainen, Damian Merrick, Cahya Ong, and Thomas Wolle. Compressing spatio-temporal trajectories. Computational Geometry: Theory & Applications, 42(9):825-841, 2009. URL: https://doi.org/10.1016/j.comgeo.2009.02.002.
  22. Leonidas J. Guibas, John E. Hershberger, Joseph S. B. Mitchell, and Jack S. Snoeyink. Approximating polygons and subdivisions with minimum-link paths. International Journal of Computational Geometry & Applications, 3(4):383-415, 1993. URL: https://doi.org/10.1142/S0218195993000257.
  23. Hiroshi Imai and Masao Iri. Computational-geometric methods for polygonal approximations of a curve. Computer Vision, Graphics, and Image Processing, 36(1):31-41, 1986. URL: https://doi.org/10.1016/S0734-189X(86)80027-5.
  24. Allan Jørgensen, Jeff M. Phillips, and Maarten Löffler. Geometric computations on indecisive points. In Algorithms and Data Structures (WADS 2011), volume 6844 of Lecture Notes in Computer Science (LNCS), pages 536-547, Berlin, Germany, 2011. Springer Berlin Heidelberg. URL: https://doi.org/10.1007/978-3-642-22300-6_45.
  25. Christian Knauer, Maarten Löffler, Marc Scherfenberg, and Thomas Wolle. The directed Hausdorff distance between imprecise point sets. Theoretical Computer Science, 412(32):4173-4186, 2011. URL: https://doi.org/10.1016/j.tcs.2011.01.039.
  26. Maarten Löffler. Data Imprecision in Computational Geometry. PhD thesis, Universiteit Utrecht, 2009. URL: https://dspace.library.uu.nl/bitstream/handle/1874/36022/loffler.pdf [cited 2019-06-15].
  27. Maarten Löffler and Wolfgang Mulzer. Unions of onions: Preprocessing imprecise points for fast onion decomposition. Journal of Computational Geometry, 5(1):1-13, 2014. URL: https://doi.org/10.20382/jocg.v5i1a1.
  28. Maarten Löffler and Jeff M. Phillips. Shape fitting on point sets with probability distributions. In Algorithms - ESA 2009, number 5757 in Lecture Notes in Computer Science (LNCS), pages 313-324, Berlin, Germany, 2009. Springer Berlin Heidelberg. URL: https://doi.org/10.1007/978-3-642-04128-0_29.
  29. Maarten Löffler and Jack S. Snoeyink. Delaunay triangulations of imprecise points in linear time after preprocessing. Computational Geometry: Theory & Applications, 43(3):234-242, 2010. URL: https://doi.org/10.1016/j.comgeo.2008.12.007.
  30. Maarten Löffler and Marc van Kreveld. Largest and smallest tours and convex hulls for imprecise points. In Algorithm Theory - SWAT 2006, volume 4059 of Lecture Notes in Computer Science (LNCS), pages 375-387, Berlin, Germany, 2006. Springer Berlin Heidelberg. URL: https://doi.org/10.1007/11785293_35.
  31. Avraham Melkman and Joseph O'Rourke. On polygonal chain approximation. In Godfried T. Toussaint, editor, Computational Morphology, volume 6 of Machine Intelligence and Pattern Recognition, pages 87-95. Elsevier Science Publishers, 1988. URL: https://doi.org/10.1016/B978-0-444-70467-2.50012-6.
  32. Jian Pei, Bin Jiang, Xuemin Lin, and Yidong Yuan. Probabilistic skylines on uncertain data. In Proceedings of the 33rd International Conference on Very Large Data Bases, pages 15-26, Los Angeles, CA, USA, 2007. VLDB Endowment. URL: https://doi.org/10.5555/1325851.1325858.
  33. Aleksandr Popov. Similarity of uncertain trajectories. Master’s thesis, Eindhoven University of Technology, November 2019. URL: https://research.tue.nl/en/studentTheses/similarity-of-uncertain-trajectories [cited 2019-12-18].
  34. 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.
  35. Subhash Suri, Kevin Verbeek, and Hakan Yıldız. On the most likely convex hull of uncertain points. In Algorithms - ESA 2013, volume 8125 of Lecture Notes in Computer Science (LNCS), pages 791-802, Berlin, Germany, 2013. Springer Berlin Heidelberg. URL: https://doi.org/10.1007/978-3-642-40450-4_67.
  36. Mees van de Kerkhof, Irina Kostitsyna, Maarten Löffler, Majid Mirzanezhad, and Carola Wenk. Global curve simplification. In 27th Annual European Symposium on Algorithms (ESA 2019), volume 144 of Leibniz International Proceedings in Informatics (LIPIcs), pages 67:1-67:14, Dagstuhl, Germany, 2019. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.ESA.2019.67.
  37. Marc van Kreveld, Maarten Löffler, and Joseph S. B. Mitchell. Preprocessing imprecise points and splitting triangulations. SIAM Journal on Computing, 39(7):2990-3000, 2010. URL: https://doi.org/10.1137/090753620.
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