Document Open Access Logo

Preference-Based Trajectory Clustering - An Application of Geometric Hitting Sets

Authors Florian Barth, Stefan Funke, Claudius Proissl

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2021.15.pdf
  • Filesize: 0.57 MB
  • 14 pages

Document Identifiers

Author Details

Florian Barth
  • Universiät Stuttgart, Germany
Stefan Funke
  • Universität Stuttgart, Germany
Claudius Proissl
  • Universität Stuttgart, Germany

Funding

This work was in part supported by the Deutsche Forschungsgemeinschaft (DFG) within the priority program 1894: Volunteered Geographic Information: Interpretation, Visualization and Social Computing.

Cite As Get BibTex

Florian Barth, Stefan Funke, and Claudius Proissl. Preference-Based Trajectory Clustering - An Application of Geometric Hitting Sets. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 15:1-15:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ISAAC.2021.15

Abstract

In a road network with multicriteria edge costs we consider the problem of computing a minimum number of driving preferences such that a given set of paths/trajectories is optimal under at least one of these preferences. While the exact formulation and solution of this problem appears theoretically hard, we show that in practice one can solve the problem exactly even for non-homeopathic instance sizes of several thousand trajectories in a road network of several million nodes. We also present a parameterized guaranteed-polynomial-time scheme with very good practical performance.

Subject Classification

ACM Subject Classification
  • Theory of computation → Discrete optimization
  • Theory of computation → Computational geometry
Keywords
  • Route planning
  • personalization
  • computational geometry

Metrics

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

Supplementary Materials

References

  1. Pankaj K Agarwal, Sariel Har-Peled, Kasturi R Varadarajan, et al. Geometric approximation via coresets. Combinatorial and computational geometry, 52:1-30, 2005. Google Scholar
  2. Noga Alon, Dana Moshkovitz, and Shmuel Safra. Algorithmic construction of sets for k-restrictions. ACM Trans. Algorithms, 2(2):153-177, 2006. Google Scholar
  3. Andrew Makhorin. GLPK - GNU Project - Free Software Foundation (FSF), 2012. URL: https://www.gnu.org/software/glpk/glpk.html.
  4. Florian Barth, Stefan Funke, Tobias Skovgaard Jepsen, and Claudius Proissl. Scalable unsupervised multi-criteria trajectory segmentation and driving preference mining. In BigSpatial@SIGSPATIAL, pages 6:1-6:10. ACM, 2020. Google Scholar
  5. Hervé Brönnimann and Michael T Goodrich. Almost optimal set covers in finite vc-dimension. Discrete & Computational Geometry, 14(4):463-479, 1995. Google Scholar
  6. Herbert Edelsbrunner. Algorithms in Combinatorial Geometry, volume 10 of EATCS Monographs on Theoretical Computer Science. Springer, 1987. Google Scholar
  7. Robert J. Fowler, Mike Paterson, and Steven L. Tanimoto. Optimal packing and covering in the plane are NP-complete. Inf. Process. Lett., 12(3):133-137, 1981. Google Scholar
  8. Stefan Funke, Sören Laue, and Sabine Storandt. Deducing individual driving preferences for user-aware navigation. In SIGSPATIAL/GIS, pages 14:1-14:9. ACM, 2016. Google Scholar
  9. Stefan Funke, Sören Laue, and Sabine Storandt. Personal routes with high-dimensional costs and dynamic approximation guarantees. In SEA, volume 75 of LIPIcs, pages 18:1-18:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. Google Scholar
  10. Stefan Funke, Kurt Mehlhorn, and Stefan Näher. Structural filtering: a paradigm for efficient and exact geometric programs. Comput. Geom., 31(3):179-194, 2005. Google Scholar
  11. Stefan Funke, André Nusser, and Sabine Storandt. On k-path covers and their applications. VLDB J., 25(1):103-123, 2016. Google Scholar
  12. Stefan Funke and Sabine Storandt. Personalized route planning in road networks. In SIGSPATIAL/GIS, pages 45:1-45:10. ACM, 2015. Google Scholar
  13. Robert Geisberger, Moritz Kobitzsch, and Peter Sanders. Route planning with flexible objective functions. In 2010 Proceedings of the Twelfth Workshop on Algorithm Engineering and Experiments (ALENEX), pages 124-137. SIAM, 2010. Google Scholar
  14. Martin Grötschel, László Lovász, and Alexander Schrijver. The ellipsoid method. In Geometric Algorithms and Combinatorial Optimization, pages 64-101. Springer, 1993. Google Scholar
  15. David S Johnson. Approximation algorithms for combinatorial problems. Journal of computer and system sciences, 9(3):256-278, 1974. Google Scholar
  16. Nabil H. Mustafa and Saurabh Ray. PTAS for geometric hitting set problems via local search. In Symposium on Computational Geometry, pages 17-22. ACM, 2009. Google Scholar
  17. Johannes Oehrlein, Benjamin Niedermann, and Jan-Henrik Haunert. Inferring the parametric weight of a bicriteria routing model from trajectories. In SIGSPATIAL/GIS, pages 59:1-59:4. ACM, 2017. Google Scholar
  18. The CGAL Project. CGAL User and Reference Manual. CGAL Editorial Board, 5.0.3 edition, 2020. URL: https://doc.cgal.org/5.0.3/Manual/packages.html.
  19. Ron Wein, Eric Berberich, Efi Fogel, Dan Halperin, Michael Hemmer, Oren Salzman, and Baruch Zukerman. 2D arrangements. In CGAL User and Reference Manual. CGAL Editorial Board, 5.0.3 edition, 2020. URL: https://doc.cgal.org/5.0.3/Manual/packages.html#PkgArrangementOnSurface2.
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