2026-08-01T15:29:16Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15448 2024-03-06T10:55:19Z ddc:004 open_access

Preference-Based Trajectory Clustering - An Application of Geometric Hitting Sets Barth, Florian Funke, Stefan Proissl, Claudius Route planning personalization computational geometry 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Florian Barth and Stefan Funke and Claudius Proissl 2021 Is Part Of LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2021.15 urn:nbn:de:0030-drops-154481 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.15 eng https://creativecommons.org/licenses/by/4.0/legalcode