3 Search Results for "Custers, Bram"

Document
DOI: 10.4230/LIPIcs.SEA.2025.7
Continuous Map Matching to Paths Under Travel Time Constraints

Authors: Yannick Bosch and Sabine Storandt

Published in: LIPIcs, Volume 338, 23rd International Symposium on Experimental Algorithms (SEA 2025)

Abstract
In this paper, we study the problem of map matching with travel time constraints. Given a sequence of k spatio-temporal measurements and an embedded path graph with travel time costs, the goal is to snap each measurement to a close-by location in the graph, such that consecutive locations can be reached from one another along the path within the timestamp difference of the respective measurements. This problem arises in public transit data processing as well as in map matching of movement trajectories to general graphs. We show that the classical approach for this problem, which relies on selecting a finite set of candidate locations in the graph for each measurement, cannot guarantee to find a consistent solution. We propose a new algorithm that can deal with an infinite set of candidate locations per measurement. We prove that our algorithm always detects a consistent map matching path (if one exists). Despite the enlarged candidate set, we also demonstrate that our algorithm has superior running time in theory and practice. For a path graph with n nodes, we show that our algorithm runs in 𝒪(k² n log {nk}) and under mild assumptions in 𝒪(k n ^λ + n log³ n) for λ ≈ 0.695. This is a significant improvement over the baseline, which runs in 𝒪(k n²) and which might not even identify a correct solution. The performance of our algorithm hinges on an efficient segment-circle intersection data structure. We describe how to design and implement such a data structure for our application. In the experimental evaluation, we demonstrate the usefulness of our novel algorithm on a diverse set of generated measurements as well as GTFS data.
Cite as

Yannick Bosch and Sabine Storandt. Continuous Map Matching to Paths Under Travel Time Constraints. In 23rd International Symposium on Experimental Algorithms (SEA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 338, pp. 7:1-7:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bosch_et_al:LIPIcs.SEA.2025.7,
  author =	{Bosch, Yannick and Storandt, Sabine},
  title =	{{Continuous Map Matching to Paths Under Travel Time Constraints}},
  booktitle =	{23rd International Symposium on Experimental Algorithms (SEA 2025)},
  pages =	{7:1--7:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-375-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{338},
  editor =	{Mutzel, Petra and Prezza, Nicola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2025.7},
  URN =		{urn:nbn:de:0030-drops-232457},
  doi =		{10.4230/LIPIcs.SEA.2025.7},
  annote =	{Keywords: Map matching, Travel time, Segment-circle intersection data structure}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2022.58
Segment Visibility Counting Queries in Polygons

Authors: Kevin Buchin, Bram Custers, Ivor van der Hoog, Maarten Löffler, Aleksandr Popov, Marcel Roeloffzen, and Frank Staals

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
Let P be a simple polygon with n vertices, and let A be a set of m points or line segments inside P. We develop data structures that can efficiently count the objects from A that are visible to a query point or a query segment. Our main aim is to obtain fast, O(polylog nm), query times, while using as little space as possible. In case the query is a single point, a simple visibility-polygon-based solution achieves O(log nm) query time using O(nm²) space. In case A also contains only points, we present a smaller, O(n + m^{2+ε} log n)-space, data structure based on a hierarchical decomposition of the polygon. Building on these results, we tackle the case where the query is a line segment and A contains only points. The main complication here is that the segment may intersect multiple regions of the polygon decomposition, and that a point may see multiple such pieces. Despite these issues, we show how to achieve O(log n log nm) query time using only O(nm^{2+ε} + n²) space. Finally, we show that we can even handle the case where the objects in A are segments with the same bounds.
Cite as

Kevin Buchin, Bram Custers, Ivor van der Hoog, Maarten Löffler, Aleksandr Popov, Marcel Roeloffzen, and Frank Staals. Segment Visibility Counting Queries in Polygons. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 58:1-58:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{buchin_et_al:LIPIcs.ISAAC.2022.58,
  author =	{Buchin, Kevin and Custers, Bram and van der Hoog, Ivor and L\"{o}ffler, Maarten and Popov, Aleksandr and Roeloffzen, Marcel and Staals, Frank},
  title =	{{Segment Visibility Counting Queries in Polygons}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{58:1--58:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.58},
  URN =		{urn:nbn:de:0030-drops-173431},
  doi =		{10.4230/LIPIcs.ISAAC.2022.58},
  annote =	{Keywords: Visibility, Data Structure, Polygons, Complexity}
}
Document
DOI: 10.4230/LIPIcs.GIScience.2021.II.7
Coordinated Schematization for Visualizing Mobility Patterns on Networks

Authors: Bram Custers, Wouter Meulemans, Bettina Speckmann, and Kevin Verbeek

Published in: LIPIcs, Volume 208, 11th International Conference on Geographic Information Science (GIScience 2021) - Part II

Abstract
GPS trajectories of vehicles moving on a road network are a valuable source of traffic information. However, the sheer volume of available data makes it challenging to identify and visualize salient patterns. Meaningful visual summaries of trajectory collections require that both the trajectories and the underlying network are aggregated and simplified in a coherent manner. In this paper we propose a coordinated fully-automated pipeline for computing a schematic overview of mobility patterns from a collection of trajectories on a street network. Our pipeline utilizes well-known building blocks from GIS, automated cartography, and trajectory analysis: map matching, road selection, schematization, movement patterns, and metro-map style rendering. We showcase the results of our pipeline on two real-world trajectory collections around The Hague and Beijing.
Cite as

Bram Custers, Wouter Meulemans, Bettina Speckmann, and Kevin Verbeek. Coordinated Schematization for Visualizing Mobility Patterns on Networks. In 11th International Conference on Geographic Information Science (GIScience 2021) - Part II. Leibniz International Proceedings in Informatics (LIPIcs), Volume 208, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{custers_et_al:LIPIcs.GIScience.2021.II.7,
  author =	{Custers, Bram and Meulemans, Wouter and Speckmann, Bettina and Verbeek, Kevin},
  title =	{{Coordinated Schematization for Visualizing Mobility Patterns on Networks}},
  booktitle =	{11th International Conference on Geographic Information Science (GIScience 2021) - Part II},
  pages =	{7:1--7:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-208-2},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{208},
  editor =	{Janowicz, Krzysztof and Verstegen, Judith A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GIScience.2021.II.7},
  URN =		{urn:nbn:de:0030-drops-147665},
  doi =		{10.4230/LIPIcs.GIScience.2021.II.7},
  annote =	{Keywords: Trajectories, Visualization, Schematization}
}
  • Refine by Type
  • 3 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2022
  • 1 2021

  • Refine by Author
  • 2 Custers, Bram
  • 1 Bosch, Yannick
  • 1 Buchin, Kevin
  • 1 Löffler, Maarten
  • 1 Meulemans, Wouter
  • Show More...

  • Refine by Series/Journal
  • 3 LIPIcs

  • Refine by Classification
  • 3 Theory of computation → Computational geometry
  • 1 Theory of computation → Design and analysis of algorithms

  • Refine by Keyword
  • 1 Complexity
  • 1 Data Structure
  • 1 Map matching
  • 1 Polygons
  • 1 Schematization
  • Show More...

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