Preference-Based Trajectory Clustering - An Application of Geometric Hitting Sets
Florian Barth, Stefan Funke, Claudius Proissl · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2021
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.