Document Open Access Logo

Approximating the Packedness of Polygonal Curves

Authors Joachim Gudmundsson, Yuan Sha, Sampson Wong

PDF

File

Thumbnail PDF
PDF
LIPIcs.ISAAC.2020.9.pdf
  • Filesize: 0.64 MB
  • 15 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Computational geometry
  • trajectories
  • realistic input models

Metrics

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

Abstract

In 2012 Driemel et al. [Anne Driemel et al., 2012] introduced the concept of c-packed curves as a realistic input model. In the case when c is a constant they gave a near linear time (1+ε)-approximation algorithm for computing the Fréchet distance between two c-packed polygonal curves. Since then a number of papers have used the model. 
In this paper we consider the problem of computing the smallest c for which a given polygonal curve in ℝ^d is c-packed. We present two approximation algorithms. The first algorithm is a 2-approximation algorithm and runs in O(dn² log n) time. In the case d = 2 we develop a faster algorithm that returns a (6+ε)-approximation and runs in O((n/ε³)^{4/3} polylog (n/ε))) time.
We also implemented the first algorithm and computed the approximate packedness-value for 16 sets of real-world trajectories. The experiments indicate that the notion of c-packedness is a useful realistic input model for many curves and trajectories.

Cite As Get BibTex

Joachim Gudmundsson, Yuan Sha, and Sampson Wong. Approximating the Packedness of Polygonal Curves. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 9:1-9:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ISAAC.2020.9

Author Details

Joachim Gudmundsson
  • The University of Sydney, Australia
Yuan Sha
  • The University of Sydney, Australia
Sampson Wong
  • The University of Sydney, Australia

References

  1. Pankaj K. Agarwal. Partitioning arrangements of lines II: applications. Discrete & Computational Geometry, 5:533-573, 1990. URL: https://doi.org/10.1007/BF02187809.
  2. Pankaj K. Agarwal, Rolf Klein, Christian Knauer, Stefan Langerman, Pat Morin, Micha Sharir, and Michael Soss. Computing the detour and spanning ratio of paths, trees, and cycles in 2D and 3D. Discrete & Computational Geometry, 39(1):17-37, 2008. Google Scholar
  3. H. Alt and M. Godau. Computing the Fréchet distance between two polygonal curves. International Journal of Computational Geometry, 5:75-91, 1995. Google Scholar
  4. Helmut Alt, Christian Knauer, and Carola Wenk. Comparison of distance measures for planar curves. Algorithmica, 38(1):45-58, 2004. Google Scholar
  5. Boris Aronov, Sariel Har-Peled, Christian Knauer, Yusu Wang, and Carola Wenk. Fréchet distance for curves, revisited. In Proceedings of the European Symposium on Algorithms (ESA), pages 52-63, 2006. Google Scholar
  6. Karl Bringmann. Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless SETH fails. In 55th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 661-670, 2014. Google Scholar
  7. Karl Bringmann and Marvin Künnemann. Improved approximation for Fréchet distance on c-packed curves matching conditional lower bounds. International Journal on Computational Geometry and Applications, 27(1-2):85-120, 2017. Google Scholar
  8. P. B. Callahan and S. R. Kosaraju. A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields. Journal of the ACM, 42(1):67–90, 1995. Google Scholar
  9. Bernard Chazelle. Reporting and counting segment intersections. Journal of Computer and System Sciences, 32(2):156-182, 1986. Google Scholar
  10. Daniel Chen, Anne Driemel, Leonidas J. Guibas, Andy Nguyen, and Carola Wenk. Approximate map matching with respect to the Fréchet distance. In Proceedings of the 13th Workshop on Algorithm Engineering and Experiments (ALENEX), pages 75-83, 2011. Google Scholar
  11. P. C. Cross, D. M. Heisey, J. A. Bowers, C. T. Hay, J. Wolhuter, P. Buss, M. Hofmeyr, A. L. Michel, R. G. Bengis, T. L. F. Bird, , et al. Disease, predation and demography: assessing the impacts of bovine tuberculosis on african buffalo by monitoring at individual and population levels. Journal of Applied Ecology, 46(2):467-475, 2009. Google Scholar
  12. R. Silverman D. Mount and A. Wu. On the area of overlap of translated polygons. Computer Vision and Image Understanding, 64(1):53-61, 1996. Google Scholar
  13. M. de Berg, O. Cheong, M. J. van Kreveld, and M. H. Overmars. Computational geometry: algorithms and applications, 3rd Edition. Springer, 2008. Google Scholar
  14. Mark de Berg. Linear size binary space partitions for uncluttered scenes. Algorithmica, 28(3):353-366, 2000. Google Scholar
  15. Mark de Berg, Frank van der Stappen, Jules Vleugels, and Matya Katz. Realistic input models for geometric algorithms. Algorithmica, 34(1):81-97, 2002. Google Scholar
  16. Anne Driemel and Sariel Har-Peled. Jaywalking your dog: Computing the Fréchet distance with shortcuts. SIAM Journal on Computing, 42(5):1830-1866, 2013. Google Scholar
  17. Anne Driemel, Sariel Har-Peled, and Carola Wenk. Approximating the Fréchet distance for realistic curves in near linear time. Discrete & Computational Geometry, 48(1):94-127, 2012. Google Scholar
  18. Anne Driemel and Amer Krivosija. Probabilistic embeddings of the Fréchet distance. In Proceedings of the 16th International Workshop Approximation and Online Algorithms, pages 218-237, 2018. Google Scholar
  19. Jeff Erickson. On the relative complexities of some geometric problems. In Proceedings of the 7th Canadian Conference on Computational Geometry, pages 85-90. Carleton University, Ottawa, Canada, 1995. URL: http://www.cccg.ca/proceedings/1995/cccg1995_0014.pdf.
  20. Elias Frentzos, Kostas Gratsias, Nikos Pelekis, and Yannis Theodoridis. Nearest neighbor search on moving object trajectories. In SSTD, pages 328-345. Springer, 2005. Google Scholar
  21. M. Maurice Fréchet. Sur quelques points du calcul fonctionnel. Rendiconti del Circolo Matematico di Palermo, 22:1-72, 1906. URL: https://doi.org/10.1007/BF03018603.
  22. Anna Gagliardo, Enrica Pollonara, and Martin Wikelski. Pigeon navigation: exposure to environmental odours prior release is sufficient for homeward orientation, but not for homing. Journal of Experimental Biology, pages jeb-140889, 2016. Google Scholar
  23. Luca Giuggioli, Thomas J McKetterick, and Marc Holderied. Delayed response and biosonar perception explain movement coordination in trawling bats. PLoS computational biology, 11(3):e1004089, 2015. Google Scholar
  24. J. Gudmundsson, M. J. van Kreveld, and F. Staals. Algorithms for hotspot computation on trajectory data. In 21st SIGSPATIAL International Conference on Advances in Geographic Information Systems, pages 134-143. ACM, 2013. Google Scholar
  25. Joachim Gudmundsson, Michael Horton, John Pfeifer, and Martin Seybold. A practical index structure supporting Fréchet proximity queries among trajectories. arXiv:2005.13773. Google Scholar
  26. Joachim Gudmundsson, Yuan Sha, and Sampson Wong. Approximating the packedness of polygonal curves, 2020. URL: http://arxiv.org/abs/2009.07789.
  27. Joachim Gudmundsson and Michiel H. M. Smid. Fast algorithms for approximate Fréchet matching queries in geometric trees. Computational Geometry, 48(6):479-494, 2015. Google Scholar
  28. Sariel Har-Peled and Benjamin Raichel. The Fréchet distance revisited and extended. ACM Transactions on Algorithms, 10(1), 2014. Google Scholar
  29. W. Meulemans K. Buchin, M. Buchin and W. Mulzer. Four soviets walk the dog - with an application to alt’s conjecture. Discrete & Computational Geometry, 58(1):180-216, 2017. Google Scholar
  30. Roland Kays, James Flowers, and Suzanne Kennedy-Stoskopf. Cat tracker project. http://www.movebank.org/, 2016.
  31. Huanhuan Li, Jingxian Liu, Ryan Wen Liu, Naixue Xiong, Kefeng Wu, and Tai-hoon Kim. A dimensionality reduction-based multi-step clustering method for robust vessel trajectory analysis. Sensors, 17(8):1792, 2017. Google Scholar
  32. Microsoft. Microsoft research asia, GeoLife GPS trajectories. http://www.microsoft.com/en-us/download/details.aspx?id=52367, 2012.
  33. Joseph S. B. Mitchell, David M. Mount, and Subhash Suri. Query-sensitive ray shooting. International Journal on Computational Geometry and Applications, 7(4):317-347, 1997. Google Scholar
  34. NOAA. National hurricane center, national oceanic and atmospheric administration, HURDAT2 atlantic hurricane database. http://www.nhc.noaa.gov/data/, 2017.
  35. Mark H. Overmars and A. Frank van der Stappen. Range searching and point location among fat objects. Journal of Algorithms, 21(3):629-656, 1996. Google Scholar
  36. Caroline L Poli, Autumn-Lynn Harrison, Adriana Vallarino, Patrick D Gerard, and Patrick GR Jodice. Dynamic oceanography determines fine scale foraging behavior of masked boobies in the gulf of mexico. PloS one, 12(6):e0178318, 2017. Google Scholar
  37. Rajiv Shah and Rob Romijnders. Applying deep learning to basketball trajectories. arXiv preprint arXiv:1608.03793, 2016. Google Scholar
  38. STATS. STATS LLC - data science. http://www.stats.com/data-science/, 2015.
  39. Frank van der Stappen and Mark H. Overmars. Motion planning amidst fat obstacles (extended abstract). In Proceedings of the 10th Annual Symposium on Computational Geometry, pages 31-40, 1994. Google Scholar
  40. Frank van der Stappen, Mark H. Overmars, Mark de Berg, and Jules Vleugels. Motion planning in environments with low obstacle density. Discrete & Computational Geometry, 20(4):561-587, 1998. Google Scholar
  41. Antoine Vigneron. Geometric optimization and sums of algebraic functions. ACM Trans. Algorithms, 10(1):4:1-4:20, 2014. URL: https://doi.org/10.1145/2532647.
  42. Martin Wikelski, Elena Arriero, Anna Gagliardo, Richard A Holland, Markku J Huttunen, Risto Juvaste, Inge Mueller, Grigori Tertitski, Kasper Thorup, Martin Wild, et al. True navigation in migrating gulls requires intact olfactory nerves. Scientific reports, 5:17061, 2015. Google Scholar
  43. Ben H Williams, Marc Toussaint, and Amos J Storkey. Extracting motion primitives from natural handwriting data. In ICANN, pages 634-643. Springer, 2006. Google Scholar
  44. Jing Yuan, Yu Zheng, Xing Xie, and Guangzhong Sun. Driving with knowledge from the physical world. In Proc. of the 17th ACM SIGKDD Conf., pages 316-324. ACM, 2011. Google Scholar
  45. Jing Yuan, Yu Zheng, Chengyang Zhang, Wenlei Xie, Xing Xie, Guangzhong Sun, and Yan Huang. T-drive: driving directions based on taxi trajectories. In Proceedings of the 18th ACM SIGSPATIAL Conference, pages 99-108. ACM, 2010. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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