DROPS

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}
}

Search Results

Documents authored by Custers, Bram

Segment Visibility Counting Queries in Polygons

Abstract

Cite as

Coordinated Schematization for Visualizing Mobility Patterns on Networks

Abstract

Cite as

Thanks for your feedback!

Could not send message