License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2021.15
URN: urn:nbn:de:0030-drops-154481
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15448/
Go to the corresponding LIPIcs Volume Portal

Barth, Florian ; Funke, Stefan ; Proissl, Claudius

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

pdf-format:
LIPIcs-ISAAC-2021-15.pdf (0.6 MB)

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.

BibTeX - Entry

@InProceedings{barth_et_al:LIPIcs.ISAAC.2021.15,
  author =	{Barth, Florian and Funke, Stefan and Proissl, Claudius},
  title =	{{Preference-Based Trajectory Clustering - An Application of Geometric Hitting Sets}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{15:1--15:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/15448},
  URN =		{urn:nbn:de:0030-drops-154481},
  doi =		{10.4230/LIPIcs.ISAAC.2021.15},
  annote =	{Keywords: Route planning, personalization, computational geometry}
}

Keywords: Route planning, personalization, computational geometry
Collection: 32nd International Symposium on Algorithms and Computation (ISAAC 2021)
Issue Date: 2021
Date of publication: 30.11.2021
Supplementary Material: Software (Source Code and Data): https://doi.org/10.17605/osf.io/4qkuv

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI